Method and device for determining the number of expired clock cycles of a binary random number gener

专利摘要:
Ein Verfahren zur Ermittlung der Anzahl DELTAÐ von zwischen zwei Zeitpunkten t¶1¶ und t¶2¶ abgelaufenen Taktzyklen eines binären Zufallsgenerators (1), der zur Erzeugung einer binären Zufallsfolge s(Ði) mit Zykluslänge n ein Schieberegister (4) mit mindestens einer an seinen Eingang (8) zurückgeführten Schieberegisterstufe (5¶1¶, 5¶2¶, ..., 5¶m¶) umfaßt, liest zu den Zeitpunkten t¶1¶ und t¶2¶ jeweils einen Zustandsvektor a(Ð1) und a(Ð2) mit den Zuständen aller Schieberegisterstufen (5¶1¶, 5¶2¶, ..., 5¶m¶) aus. Die Zustandsvektoren a(Ð1) und a(Ð2) werden anschließend jeweils mit einer gegenüber der maximal möglichen Anzahl n von Vergleichszustandsvektoren a¶REF¶(Ði) reduzierten Anzahl n' von Vergleichszustandsvektoren a¶REF¶'(Ðil) verglichen. Bei Identität zwischen den Zustandsvektoren a(Ð1) und a(Ð2) und einem der n' Vergleichszustandsvektoren a¶REF¶'(Ðil) wird der jeweils zugehörige Taktzyklus Ð1 und Ð2 ermittelt und aus der Differenz der Taktzyklen Ð1 und Ð2 die Anzahl DELTAÐ von abgelaufenen Taktzyklen berechnet.A method for determining the number of DELTAÐ of between two times t¶1¶ and t¶2¶ expired clock cycles of a binary random number generator (1), which generates a binary random sequence s (Ði) with cycle length n a shift register (4) with at least one comprises at its input (8) fed back shift stage (5¶1¶, 5¶2¶, ..., 5¶m¶), reads at the times t¶1¶ and t¶2¶ each a state vector a (Ð1) and a (Ð2) with the states of all shift register stages (5¶1¶, 5¶2¶, ..., 5¶m¶). The state vectors a (Ð1) and a (Ð2) are then each compared with a reduced number n 'of comparison state vectors a¶REF¶' (Ðil) compared to the maximum possible number n of comparison state vectors a¶REF¶ (Ð). In the case of identity between the state vectors a (Ð1) and a (Ð2) and one of the n 'comparison state vectors a¶REF¶' (Ðil), the respectively associated clock cycle Ð1 and Ð2 is determined and from the difference of the clock cycles Ð1 and Ð2 the number DELTAÐ of calculated clock cycles.
公开号:DE102004022647A1
申请号:DE200410022647
申请日:2004-05-07
公开日:2005-12-22
发明作者:Otmar Wanierke
申请人:Rohde and Schwarz GmbH and Co KG；
IPC主号:G06F7-58

专利说明:
[0001] DieErfindung betrifft ein Verfahren und eine Vorrichtung zur Ermittlungder Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators.TheThe invention relates to a method and a device for detectionthe number Δτ of expiredClock cycles of a binaryRandom generator.
[0002] Einewichtige Forderung, die an ein Datenübertragungssystem gestelltwird, ist die Unabhängigkeit seinerEigenschaften von den zu übertragendenDaten. So könnenbeispielsweise sich ständigwiederholende Bitfolgen oder lange Folgen von "Nullen" oder "Einsen" zu deutlichen Unterschieden im Empfangspegel,zu Problemen bei der Taktrückgewinnungund gegebenenfalls auch zu Schwierigkeiten bei einer adaptiven Entzerrungführen.Alle diese Probleme treten jedoch nicht auf, wenn die Bitfolgenpseudozufälligsind und keine erkennbaren Bitmuster vorhanden sind. Diese Forderungführt dazu,daß vieleDatenübertragungssystemeeinen binärenZufallsgenerator (Scrambler) enthalten, der eine binäre Zufallsfolgegeneriert, mit der aus jeder beliebigen Eingangsbitfolge eine pseudozufällige Ausgangsbitfolgeerzeugt wird, die am Ende der Datenübertragungsstrecke mit eineminversen binärenZufallsgenerator (Descrambler) wieder in die ursprünglicheEingangsbitfolge zurückgeführt wird.Aimportant requirement placed on a data transmission systemis the independence of hisProperties of those to be transferredDates. So canfor example, constantlyrepeating bit sequences or long sequences of "zeroes" or "ones" to distinct differences in the reception level,to problems with clock recoveryand possibly also difficulties with adaptive equalizationto lead.However, all these problems do not occur when the bit stringspseudorandomand there are no recognizable bit patterns. This requirementleads to,that manyData transmission systemsa binary oneRandomizer (scrambler) containing a binary random sequencegenerates a pseudorandom output bit sequence from any input bitstreamgenerated at the end of the data transmission path with ainverse binaryRandomizer (Descrambler) back to the original oneInput bit sequence is returned.
[0003] DerartigebinäreZufallsgeneratoren werden überSchieberegister, wie z. B. in der DE 41 39 630 A1 dargestellt, realisiert,bei denen zur Erzeugung einer binären Zufallsfolge am Ausgangdes Schieberegisters eine oder mehrere Schieberegisterstufen anden Eingang des Schieberegisters zurückgekoppelt werden. Die binäre Zufallsfolgeweist eine von der Konfiguration der Rückkopplungen des SchieberegistersabhängigePeriodizitätauf. Die Zykluslängen der binärenZufallsfolge ist bei einem Schieberegister mit m Schieberegisterstufenmaximal 2^m – 1 Takte lang.Such binary random number generators are via shift registers, such. B. in the DE 41 39 630 A1 shown, realized in which to generate a binary random sequence at the output of the shift register, one or more shift register stages are fed back to the input of the shift register. The binary random sequence has a periodicity dependent on the configuration of the feedback of the shift register. The cycle length n of the binary random sequence is a maximum of 2 ^m - 1 clock in the case of a shift register with m shift register stages.
[0004] Nebender Generierung einer binärenZufallsfolge kann, wie im folgenden gezeigt wird, ein binärer Zufallsgenerator auchzur Zeitüberwachungin einem Datenübertragungssystem,beispielsweise zur zeitlichen Erfassung einer Störung in einer Busstation desDatenübertragungssystems,eingesetzt werden. Derartige Aufgaben wurden bisher durch in Seriegeschaltete Zählerwahrgenommen, deren Zählerstände einMaß für die abgelaufeneZeitdauer darstellen. Nachteilig an einer derartigen Realisierungist der hohe Hardware-Aufwand mitvielen gekoppelten Zählerbausteinen,falls der durch die gekoppelten Zähler abzudeckende Zeitüberwachungshorizontwie im Falle einer Betriebsüberwachungder Datenübertragungsstreckevergleichsweise groß ist.Auch stellt das gleichzeitige Rücksetzenmehrerer Zählerbei Überlaufder Zählerkombinationeine nicht unbedeutende Fehlerquelle dar, da ein fehlerhaftes Bit-Kippen beim gleichzeitigenRücksetzeneiner Vielzahl von Bitstellen nicht unwahrscheinlich ist.Nextthe generation of a binaryRandom sequence can also be a binary random number generator, as shown belowfor time monitoringin a data transmission system,For example, for the time detection of a fault in a bus station of theData transmission system,be used. Such tasks have been through in seriesswitched countersperceived their meter readingsMeasure of the expiredTime duration. A disadvantage of such a realizationis the high hardware effort withmany coupled counter modules,if the timeout horizon to be covered by the paired countersas in the case of operational monitoringthe data transmission linkis comparatively large.Also provides the simultaneous resetseveral countersat overflowthe counter combinationa not insignificant source of error because of a bad Bit-tilting at the same timereseta multitude of bit positions is not unlikely.
[0005] EinbinärerZufallsgenerator kann zur Zeitüberwachungeingesetzt werden, indem die Zustände aller Schieberegisterstufenzu Beginn und am Ende der Zeitüberwachungzur Bildung jeweils eines Zustandsvektors ausgelesen werden undmit allen möglichenZustandsvektoren des rückgekoppeltenSchieberegisters, die in einem Speicher abgelegt sind, verglichenwerden. Bei Identitätder beiden ausgelesenen Zustandsvektoren mit jeweils einem der abgespeichertenVergleichszustandsvektoren werden die zu den abgespeicherten Vergleichszustandsvektorenkorrepondierenden Taktzyklen, derren Differenz ein Maß für das abgelaufeneZeitintervall darstellt, ermittelt. Auf diese Weise liegt eine gegenüber derZähler-Lösung hardwareminimierteRealisierung zur Ermittlung eines Zeitintervalls – ein rückgekoppeltesSchieberegister – vor.Auch die Wahrscheinlichkeit eines fehlerhaften Bit-Kippens ist minimiert,da nur ein Bit in den einzelnen Schieberegisterstufen verarbeitetwird.OnebinaryRandom generator can be used for time monitoringbe used by changing the states of all shift register stagesat the beginning and at the end of the time monitoringfor the formation of each state vector are read andwith all possibleState vectors of the feedbackShift registers stored in a memory comparedbecome. In identitythe two read state vectors each with one of the storedComparison state vectors become the stored comparison state vectorscorresponding clock cycles, whose difference is a measure of the expiredTime interval represents determined. In this way, one lies opposite theCounter solution hardware minimizedRealization to determine a time interval - a feedbackShift register - in front.The probability of erroneous bit-tilting is also minimized,because only one bit is processed in the individual shift register stagesbecomes.
[0006] DerbinäreZufallsgenerator ist aber in seiner Anwendung als Zeitmesser durcheinen vergleichsweise hohen Aufwand beim Vergleich der ausgelesenenZustandsvektoren mit allen abgespeicherten Vergleichszustandsvektorengekennzeichnet. Bei höherstufigenSchieberegistern kann dieser Suchprozeß bis zu 2^m – 1 Suchschrittebeinhalten, was i.a. bei Echtzeitanwendungen nicht praktikabel ist.However, the binary random number generator is characterized in its application as a timer by a comparatively high outlay when comparing the read-out state vectors with all the stored comparison state vectors. For higher-level shift registers, this search process can contain up to 2 ^m - 1 search steps, which is not practical in real-time applications.
[0007] DerErfindung liegt deshalb die Aufgabe zugrunde, einen Verfahren undeine Vorrichtung zur Zeitüberwachungin Datenübertragungssystemenderart weiterzuentwickeln, daß derSuchaufwand gegenüberder obig dargestellten Situation im Hinblick auf einen sicherenEchtzeiteinsatz deutlich reduziert ist.Of theThe invention is therefore based on the object, a method anda device for time monitoringin data transmission systemsin such a way that theSearch effort comparedthe situation described above with regard to a safeReal-time use is significantly reduced.
[0008] DieErfindung wird durch ein Verfahren zur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 1 und durch eine Vorrichtung zurErmittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 10 gelöst.TheInvention is achieved by a method for determining the number Δτ of expiredClock cycles of a binaryRandom generator according to claim 1 and by a device forDetermination of the number Δτ of expiredClock cycles of a binaryRandom generator according to claim 10.
[0009] Daserfindungsgemäße Verfahrenund die erfindungsgemäße Vorrichtungzur Ermittlung der Anzahl von abgelaufenen Taktzyklen in einem binären Zufallsgeneratorreduziert den Suchaufwand, indem der Vergleich zwischen den beidenausgelesenen Zustandsvektoren und einer gegenüber der maximal möglichenAnzahl von abgespeicherten Vergleichszustandsvektoren reduziertenAnzahl von abgespeicherten Vergleichszustandsvektoren stattfindet.The inventive method and the inventive device for determining the number of elapsed clock cycles in a binary random number generator reduces the search effort by the Ver equal between the two read out state vectors and compared to the maximum possible number of stored comparison state vectors reduced number of stored comparison state vectors takes place.
[0010] Hierbeiwerden bestimmte Periodizitätenin der Zykluslängen der binärenZufallsfolge des binärenZufallsgenerators ausgenutzt. Jede Zykluslänge n läßt sich nämlich in ein Produkt von insgesamtj teilerfremden ganzzahligen Faktoren p_l zerlegen.Wie weiter unten gezeigt wird, weisen jeweils um den Faktor n/p_l zeitlich verschobene Zustandsvektoren einePeriodizitätvon p_l Zustandsvektoren auf. Für jedender insgesamt j teilerfremden Faktoren p_l istfolglich nach zeitlicher Verschiebung der Zustandsvektoren um denFaktor n/p_l nur noch ein Vergleich mit insgesamtp_l Vergleichszustandsvektoren erforderlich.In this case, certain periodicities in the cycle length n of the binary random sequence of the binary random number generator are utilized. Namely, each cycle length n can be decomposed into a product of a total of j non-divisive integer factors p _l . As will be shown below, time-shifted state vectors each have a periodicity of p _l state vectors by the factor n / p _l . For each of the j prime factors p _l of the state vectors by the factor n / p _l only a comparison with a total of p _l comparison state vectors is necessary therefore to temporal displacement.
[0011] Ausden fürjeden der j teilerfremden Faktoren p_l durcheinen reduzierten Suchvorgang ermittelten Taktzyklen τ1l und τ2l, korrespondierenddem Beginn und dem Ende des zu messenden Zeitintervalls, kann gemäß dem chinesischenRestklassensatz eindeutig jeweils ein einziger Taktzyklus τ1 und τ2, derenDifferenz der Anzahl von abgelaufenen Taktzyklen entspricht, ermitteltwerden. Die insgesamt durchzuführendeAnzahl n' von Zustandsvektorvergleichendes erfindungsgemäßen Verfahrenbzw. der erfindungsgemäßen Vorrichtungist demnach selbst bei einer Zerlegung der Zyklenlänge n ineine Vielzahl teilerfremder Faktoren p_l gegenüber denn bisher durchzuführendenVergleichen des Stands der Technik deutlich reduziert.From the clock pulses τ1l and τ2l determined by a reduced search procedure for each of the divisive factors p _l , corresponding to the beginning and the end of the time interval to be measured, one single clock cycle τ1 and τ2, whose difference corresponds to the number of times, can be uniquely determined according to the Chinese remainder theorem elapsed clock cycles are determined. The total number n 'of state vector comparisons of the method according to the invention and the device according to the invention is therefore significantly reduced even in the case of a decomposition of the cycle length n into a multiplicity of divisive factors p ₁ compared to the n comparisons of the prior art to date.
[0012] VorteilhafteAusgestaltungen der Erfindung sind in den abhängigen Ansprüchen angegeben.advantageousEmbodiments of the invention are specified in the dependent claims.
[0013] Fällt derBeginn des zu vermessenden Zeitintervalls mit der Initialisierungdes binärenZufallsgenerators zusammen, so ist nur der Zustandsvektor am Endedes zu vermessenden Zeitintervalls auszulesen und mit den Vergleichszustandsvektorenzu vergleichen, um den zum Zustandsvektor am Ende des Zeitintervalls gehörigen Taktzyklus τ2 zu ermitteln,der der Anzahl Δτ an abgelaufenenTaktzyklen des binärenZufallsgenerator entspricht.Does that fallStart of the time interval to be measured with the initializationof the binaryRandom generator together, so only the state vector is at the endof the time interval to be measured and with the comparison state vectorscompare to determine the clock cycle τ2 associated with the state vector at the end of the time interval,the number of Δτ at expiredClock cycles of the binaryRandom generator corresponds.
[0014] Für alle teillerfremdenFaktoren p_l der Zykluslänge n der binären Zufallsfolge,die sich aus der Struktur der Rückkopplungendes Schieberegisters ergibt, könnenin einer ersten Ausführungsformdes erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators die Vergleichszustandsvektoren a_REF'(τil) erst bei Bedarf im Rahmender Zeitmessung übereine iterative Berechnung ermittelt werden.For all non-external factors p _{l of} the cycle length n of the binary random sequence resulting from the structure of the feedback of the shift register, the comparison state vectors a _REF '(τil ) can only be determined if necessary during the time measurement via an iterative calculation.
[0015] Alternativkönnenin einer zweiten Ausführungsformdes erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators sämtlichen' Vergleichszustandsvektorena_REF'(τil) vorabberechnet werden. Diese vorab berechneten Vergleichszustandsvektorenkönnenin einem Speicher abgelegt werden und bei Bedarf zur Durchführung desSuchvorgangs im Rahmen der Zeitmessung herangezogen werden.Alternatively, in a second embodiment of the inventive method for determining the number Δτ of elapsed clock cycles of a binary random number generator, all n 'comparison state vectors a _REF ' (τil) can be calculated in advance. These previously calculated comparison state vectors can be stored in a memory and, if necessary, used to carry out the search within the scope of the time measurement.
[0016] ZurReduzierung des Suchprozesses könnenbinäreSuchalgorithmen überEntscheidungsbäume oderHash-Algorithmen eingesetzt werden.toCan reduce the search processbinarySearch algorithms overDecision trees orHash algorithms are used.
[0017] EineZwischenform zwischen einer Vorabberechnung und Speicherung derVergleichszustandsvektoren – Offline-Lösung – und einer am Bedarf zeitnahen,iterativen Berechnung der Vergleichszustandsvektoren – Online-Lösung – liegtbei der dritten Ausführungsformdes erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators in der Vorabberechnung und Speicherung lediglicheiner Teilmenge der Vergleichszustandvektoren. Falls im Bedarfsfallder durchzuführendenZeitmessung die ausgelesenen Zustandsvektoren mit den nur teilweiseabgespeicherten Vergleichsvektoren nicht übereinstimmen, werden die ausgelesenenZustandsvektoren zyklisch um die Anzahl der abgespeicherten Vergleichszustandsvektorenzeitlich verschoben und die somit zeitlich verschobenen ausgelesenenZustandsvektoren mit den nur teilweise abgespeicherten Vergleichszustandsvektorenverglichen, bis ein zum zeitlich verschobenen ausgelesenen Zustandsvektoridentischer Vergleichszustandsvektor gefunden ist. Diese Zwischenformwird insbesondere bei betragsmäßig großen teilerfremdenFaktoren p_l, zu denen eine Vielzahl an zuuntersuchenden Vergleichszustandsvektoren gehört, angewendet, um die Anzahlan abzuspeichernden Vergleichszustandsvektoren zu reduzieren.An intermediate form between a preliminary calculation and storage of the comparison state vectors - offline solution - and an on-demand, iterative calculation of the comparison state vectors - online solution - is in the third embodiment of the inventive method for determining the number .DELTA.t of elapsed clock cycles of a binary random number generator in the Precalculation and storage of only a subset of the comparison state vectors. If, in case of need of the time measurement to be carried out, the read state vectors do not coincide with the comparison vectors stored only partially, the read state vectors are cyclically shifted by the number of stored comparison state vectors and the temporally shifted read-out state vectors are compared with the only partially stored comparison state vectors until a time shifted read state vector identical comparison state vector is found. This intermediate form is in particular in terms of amount large prime factors p _l, to which a plurality of part to be examined comparison state vectors, used to reduce the number of state vectors to be stored comparison.
[0018] Diedrei Ausführungsformendes erfindungsgemäßen Verfahrensund der erfindungsgemäßen Vorrichtungzur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators werden nachfolgend unter Bezugnahme auf die Zeichnungnäher erläutert. Inder Zeichnung zeigen:Thethree embodimentsthe method according to the inventionand the device according to the inventionfor determining the number Δτ of expiredClock cycles of a binaryRandom number generators are described below with reference to the drawingsexplained in more detail. Inshow the drawing:
[0019] 1 einBlockschaltbild einer erfindungsgemäßen Vorrichtung zur Ermittlungder Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgenerators, 1 a block diagram of a device according to the invention for determining the number of elapsed clock cycles of a binary random number generator,
[0020] 2 einFlußdiagrameines erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgenerators, 2 1 is a flow diagram of a method according to the invention for determining the number of expired clock cycles of a binary random number generator;
[0021] 2A einTeilflußdiagrammdes Flußflußdiagrammsin 2 füreine erste Ausführungsformeines erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgenerators, 2A a partial flowchart of the flowchart in 2 for a first embodiment of a method according to the invention for determining the number of elapsed clock cycles of a binary random number generator,
[0022] 2B einTeilflußdiagrammdes Flußflußdiagrammsin 2 füreine zweite Ausführungsformeines erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgeneratorsund 2 B a partial flowchart of the flowchart in 2 for a second embodiment of a method according to the invention for determining the number of elapsed clock cycles of a binary random number generator and
[0023] 2C einTeilflußdiagrammdes Flußflußdiagrammsin 2 füreine dritte Ausführungsformeines erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgenerators. 2C a partial flowchart of the flowchart in 2 for a third embodiment of a method according to the invention for determining the number of elapsed clock cycles of a binary random number generator.
[0024] Dieerfindungsgemäße Vorrichtungzur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen in einem binärenZufallsgenerator in 1 umfaßt einen binären Zufallsgenerator 1,eine Rechnereinheit 2 und eine Anzeige-Einrichtung 3 zurDarstellung der Ergebnisse. Der binäre Zufallsgenerator zur Erzeugungeiner binärenZufallsfolge, welche eine Periodizität der Zykluslänge n aufweist,ist überein Schieberegister 4 mit mehreren aus D-Flip-Flop-Bausteinenrealisierten Schieberegisterstufen 5₁ , 5₂ , 5₃ ,... und 5_m , im dargestellten Beispielin 1 den Schieberegisterstufen 5₁ , 5₂ , 5₃ , 5₄ , 5₅ , 5₆ und 5₇ ,verwirklicht. Zur Erzeugung einen pseudozufälligen Binärfolge mit einer bestimmtenZykluslängen am Ausgang 6 des Schieberegisters 1 sind die Ausgänge vondefinierten Schieberegisterstufen, im dargestellten Beispiel in 1 dieAusgängeder Schieberegisterstufen 5₄ , 5₆ und 5₇ über einenModulus-2-Addierer 7 an den Eingang 8 des Schieberegisters 1 rückgekoppelt.The inventive device for determining the number Δτ of elapsed clock cycles in a binary random number generator in 1 includes a binary random number generator 1 , a computer unit 2 and a display device 3 to present the results. The binary random number generator for generating a binary random sequence which has a periodicity of the cycle length n is via a shift register 4 with several shift register stages realized from D flip-flop devices 5 ₁ . 5 ₂ . 5 ₃ , ... and 5 _m , in the example shown in FIG 1 the shift register stages 5 ₁ . 5 ₂ . 5 ₃ . 5 ₄ . 5 ₅ . 5 ₆ and 5 ₇ , realized. To generate a pseudo-random binary sequence with a specific cycle length n at the output 6 of the shift register 1 are the outputs of defined shift register stages, in the example shown in FIG 1 the outputs of the shift register stages 5 ₄ . 5 ₆ and 5 ₇ via a modulus 2 adder 7 to the entrance 8th of the shift register 1 fed back.
[0025] DieBinärzustände an denAusgängenaller Schieberegisterstufen 5₁ , 5₂ , .. und 5_m desSchieberegisters 1 werden am Beginn t₁ undam Ende t₂ des zu vermessenden Zeitintervalls Δt von einerbinärenEin-/Ausgabe-Baugruppe 9 der Rechnereinheit 2 eingelesenund als Zustandvektoren a(τ1)und a(τ2)einer Prozessoreinheit (CPU) 10 zur Weiterverarbeitungin Echtzeit, wie weiter unten gezeigt wird, zugeführt. DieArgumente τ1und τ2 derZustandvektoren a(τ)stellen den Taktzyklus des binärenZufallsgenerators 1 zum Zeitpunkt t₁ (Beginndes zu vermessenden Zeitintervalls Δt) und zum Zeitpunkt t₂ (Ende des zu vermessenden Zeitintervalls Δt) dar. Diezum Zeitpunkt t₁ und t₂ eingelesenenZustandsvektoren a(τ1)und a(τ2)werden im Rahmen der Weiterverarbeitung durch die Prozessoreinheit 10 mitVergleichszustandsvektoren a'(τi) verglichen,die in einem Speicherbaustein (RAM) 11 abgelegt sind. Hierbeistellt das Argument τialle währendeiner Zykluslänge nder pseudozufälligenBinärfolgevorkommenden Taktzyklen dar.The binary states at the outputs of all shift register stages 5 ₁ . 5 ₂ , .. and 5 _m of the shift register 1 are at the beginning t ₁ and at the end t _{2 of} the time interval .DELTA.t to be measured by a binary input / output module 9 the computer unit 2 read in and as state vectors a (τ1) and a (τ2) of a processor unit (CPU) 10 for further processing in real time as shown below. The arguments τ1 and τ2 of the state vectors a (τ) represent the clock cycle of the binary random number generator 1 at time t ₁ (beginning of the time interval Δt to be measured) and at time t ₂ (end of the time interval Δt to be measured). The state vectors a (τ1) and a (τ2) read in at time t ₁ and t ₂ are used in the context of Further processing by the processor unit 10 compared with comparison state vectors a '(τi) stored in a memory device (RAM) 11 are stored. Here, the argument τi represents all clock cycles occurring during a cycle length n of the pseudo-random binary sequence.
[0026] Bevordas in 2 dargestellte erfindungsgemäße Verfahren zur Ermittlungder Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators 1 weiter unter im einzelnen vorgestelltwird, werden im folgenden die fürdas Verständnisdes erfindungsgemäßen Verfahrenserforderlichen grundlegenden mathematischen Zusammenhänge hergeleitet: DieBinärzustandeder Schieberegisterstufen 5₁ , 5₂ bis 5_m desSchieberegisters 4 zum Taktzyklus τi werden jeweils durch die Koeffizientena₁(τi),a₂(τi)bis a_m(τi)des Zustandvektor a(τ_i) gemäß Gleichung(1) beschrieben: a(τi) = (a₁(τi),a₂(τi),..., a_m(τi)) (1) Before that in 2 illustrated inventive method for determining the number Δτ of elapsed clock cycles of a binary random number generator 1 will be presented in detail below, the basic mathematical relationships required for understanding the method according to the invention are derived below: The binary states of the shift register stages 5 ₁ . 5 ₂ to 5 _m of the shift register 4 For the clock cycle τi, the state vectors a (τ _i ) according to equation (1) are respectively described by the coefficients a ₁ (τi), a ₂ (τi) to a _m (τi): a (τ i) = (a ₁ (τi), a ₂ (τi), ..., a _m (τi)) (1)
[0027] Mitjeder aktiven Flanke des Taktes (Clk) – im dargestellten Beispielder 1 mit jeder positiven Flanke des Taktes (Clk) – übernimmtjede Schieberegisterstufe 5₂ , 5₃ bis 5_m mitAusnahme der Schieberegisterstufe 5₁ amEingang 8 des Schieberegisters 4 an ihren Ausgangden bisherigen Binärzustandam Ausgang ihrer Vorgänger-Schieberegisterstufe 5₁ , 5₂ bis 5_m–1 .Der Binärzustanda_j(τ(i+ 1)) der j-ten Schieberegisterstufe 5_j des Schieberegisters 4 zumTaktzyklus τ(i+ 1) ergibt sich gemäß der oberenZeile von Gleichung (2) aus dem Binärzustand a_j–1(τi) ihrerVorgänger-Schieberegisterstufe – j–1-te Schiebneregisterstufe 5_j–1 – zum Taktzyklus τi.With each active edge of the clock (Clk) - in the example shown the 1 with each positive edge of the clock (Clk) - takes over each shift register stage 5 ₂ . 5 ₃ to 5 _m with the exception of the shift register stage 5 ₁ at the entrance 8th of the shift register 4 at its output the previous binary state at the output of its predecessor shift register stage 5 ₁ . 5 ₂ to 5m _-1 , The binary state a _j (τ (i + 1)) of the j th shift register stage 5 _y of the shift register 4 to the clock cycle τ (i + 1) results according to the upper line of equation (2) from the binary state a _j-1 (τi) of its predecessor shift register stage - j-1-th shift register stage 5 _j-1 - to the clock cycle τi.
[0028] DieSchieberegisterstufe 5₁ am Eingangdes Schieberegisters 4 übernimmtbei aktiver Flanke des Taktes (Clk) an ihrem Ausgang die über denModulus-2-Addierer 7 addierten bisherigen Binärzustände derAusgängealler rückgekoppeltenSchieberegisterstufen. Welcher Ausgang einer Schieberegisterstufe 5_i des Schieberegisters 4 über denModulus-2-Addierer 7 an den Eingang 8 des Schieberegisters 4 rückgekoppeltwird, wird gemäß Gleichung(3) überden zugehörigenKoeffizienten g_j des Vektors g festgelegt,der im Fall einer Rückkopplungdes Binärzustandsdes Ausgangs der j-ten Schieberegisterstufe 5_j denWert "l" und im Fall einer NichtrückkopplungRückkopplungdes Binärzustandsdes Ausgangs der j-ten Schieberegisterstufe 5_j denWert "0" aufweist: g = (g₁,g₂, ..., g_m) (3) The shift register stage 5 ₁ at the input of the shift register 4 takes over on active edge of the Tak tes (Clk) at its output via the modulo 2 adder 7 added previous binary states of the outputs of all feedback shift register stages. Which output of a shift register stage 5 _i of the shift register 4 via the modulo 2 adder 7 to the entrance 8th of the shift register 4 is determined according to equation (3) via the associated coefficient g _{j of} the vector g, which in the case of a feedback of the binary state of the output of the j-th shift register stage 5 _y the value "l" and in the case of non-feedback, feedback of the binary state of the output of the j-th shift register stage 5 _y has the value "0": g = (g ₁ , g ₂ , ..., g _m ) (3)
[0029] DurchBildung eines Skalarprodukts zwischen dem Vektor g und dem Zustandsvektora(τi) gemäß der unterenZeile von Gleichung (2) wird die Funktion der Rückkopplung von Binärzuständen anAusgängenbestimmter durch die Koeffizienten g_j desVektors g festgelegter Schieberegisterstufen 5_j undderen binäreAddition mittels Modulus-2-Addierer 7 mathematischbeschrieben.G by forming an inner product between the vector and the state vector a (τi) according to the bottom line of equation (2) the function of the feedback of certain binary states at outputs _j g by the coefficients of the vector g fixed shift register stages 5 _y and their binary addition by means of modulus 2 adders 7 described mathematically.
[0030] Gemäß Gleichung(4) ergibt sich die binäreZufallsfolge s(τi)zu den einzelnen Taktzyklen τiaus Binärzuständen a_m(τi)der Schieberegisterstufe 5_m amAusgang 6 des Schieberegisters 4 zu den einzelnenTaktzyklen τi. s(τi) = a_m(τi) (4) According to equation (4), the binary random sequence s (τi) at the individual clock cycles τi results from binary states a _m (τi) of the shift register stage 5 _m at the exit 6 of the shift register 4 to the individual clock cycles τi. s (τ i) = a _m (τi) (4)
[0031] Dader Vektor s(τi)für einedefinierte Anzahl von Taktzyklen τidem Zustandvektor a(τi)entspricht, kann fürdas erfindungsgemäße Verfahrenzur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binären Zufallsgeneratorsim folgenden anstelle des parallelen Auslesens der Binärzustände a_j(τi)an den Ausgängen allerSchieberegisterstufen 5_j auch derVektor s(τi)der binärenZufallsfolge am Ausgang 6 des Schieberegisters 4 sequentiellausgelesen werden.Since the vector s (τi) for a defined number of clock cycles τi the state vector a (τi), for the inventive method for determining the number .DELTA.τ of elapsed clock cycles of a binary random generator in the following instead of the parallel readout of the binary states a _j (τi ) at the outputs of all shift register stages 5 _y also the vector s (τi) of the binary random sequence at the output 6 of the shift register 4 be read out sequentially.
[0032] DerZustandsvektor a(τ(i+ 1)) des Schieberegisters 4 zu einem Taktzyklus, der genaueinen Taktzyklus späterals der Taktzyklus τiliegt, kann aus Gleichung (1) unter Zuhilfenahme der Beziehungenin Gleichung (2) übereine Verschiebematrix V aus dem Zustandsvektor a(τi) des Schieberegisters 4 zumTaktzyklus τientsprechend Gleichung (5) ermittelt werden. a(τ(i + 1)) = V·a(τi) (5) The state vector a (τ (i + 1)) of the shift register 4 to a clock cycle which is exactly one clock cycle later than the clock cycle τi can be obtained from equation (1) by using the relationships in equation (2) via a shift matrix V from the state vector a (τi) of the shift register 4 to the clock cycle τi according to equation (5) are determined. a (τ (i + 1)) = V · a (τ i) (5)
[0033] DieKoeffizienten der Verschiebematrix V ergeben sich dabei unter Zuhilfenahmeder Beziehungen in Gleichung (2) entsprechend Gleichung (6).TheCoefficients of the displacement matrix V result with the aid of thisof relations in equation (2) according to equation (6).
[0034] Umden Zustandsvektor a(τ(i+ x)) des Schieberegisters 4 zu einem Taktzyklus, der uminsgesamt x Taktzyklen späterals der Taktzyklus τiliegt, zu bestimmen, wird eine x-malige Matrizenmultiplikation desZustandsvektor a(τi)des Schieberegisters 4 zum Taktzyklus τi mit der Verschiebematrix Ventsprechend Gleichung (7) durchgeführt. a(τ(i+ x)) = V^x·a(τi) (7) To the state vector a (τ (i + x)) of the shift register 4 to a clock cycle which is a total of x clock cycles later than the clock cycle τi, an x-times matrix multiplication of the state vector a (τi) of the shift register is made 4 to the clock cycle τi with the shift matrix V according to equation (7). a (τ (i + x)) = V ^x · A (τi) (7)
[0035] Für die x-maligmultiplizierte Verschiebematrix V wird gemäß Gleichung (8) die SubstitutionsmatrixK mit den Spaltenvektoren k_i eingeführt: V^x =K = [k₁ k₂ k_i k_m] (8) For the displacement matrix V multiplied x times, the substitution matrix K with the column vectors k _{i is} introduced according to equation (8): V ^x = K = [k ₁ k ₂ k _i k _m ] (8th)
[0036] Einzum Taktzyklus τium insgesamt x Taktzyklen zeitlich verschobener Zustandsvektor a(τ(i + x))des Schieberegisters 4 kann aus einem Zustandsvektor a(τi) zum Taktzyklus τi gemäß Gleichung(9) ermittelt werden, welche aus der Kombination von Gleichung (8)mit Gleichung (7) hervorgeht: a(τ(i+ x)) = K·a(τi) (9) A state vector a (τ (i + x)) of the shift register which is shifted in time by x clock cycles relative to the clock cycle τi 4 can be determined from a state vector a (τi) at the clock cycle τi according to equation (9), which results from the combination of equation (8) with equation (7): a (τ (i + x)) = K · a (τ i) (9)
[0037] Wirdvorausgesetzt, daß aufgrundder Struktur der Rückkopplungeneines m-stufigen Schieberegisters die Zykluslänge n der durch das rückgekoppelteSchieberegister erzeugten binärenZufallsfolge gleich 2^m – 1 ist, so kann gemäß Gleichung(10) folgende Periodizitätsbedingungfestgehalten werden: a(τ(i + n))= a(τi) (10) Assuming that due to the structure of the feedbacks of an m-stage shift register, the cycle length n of the binary random sequence generated by the feedback shift register is equal to 2 ^m -1, the following periodicity condition can be stated according to equation (10): a (τ (i + n)) = a (τ i) (10)
[0038] JedeZykluslängen der erzeugten binärenZufallsfolge kann gemäß Gleichung(11) in ein Produkt von insgesamt u teilerfremden ganzzahligen Faktorenp_l zerlegt werden, wobei alle teilerfremdenFaktoren p_l nur Werte größer als eins annehmen können.Each cycle length n of the generated binary random sequence can be decomposed according to equation (11) into a product of a total of u-divisive integer factors p _l , whereby all non-divisive factors p _l can only assume values greater than one.
[0039] Ganzwesentlich fürden Erfindungsgedanken ist die Tatsache, daß mittels Substitution desArguments τidurch die Transformierte τi·n/p_l im Zustandsvektor a(τi) gemäß Gleichung (12) ein zeitlichverschobener Zustandsvektor a'(τi) entsteht,der eine kürzerePeriodizitätals die Periodizitätn des Zustandsvektors a(τi)aufweist. a'(τi) = a(τi·n/p_l) (12) Quite essential to the idea of the invention is the fact that by means of substitution of the argument τi by the transform τi · n / p _l in the state vector a (τi) according to equation (12), a time-shifted state vector a '(τi) is produced which has a shorter periodicity as the periodicity n of the state vector a (τi). a '(τ i) = a (τ i · n / p _l ) (12)
[0040] NachGleichung (13) weist der zeitlich verschobene Zustandsvektor a'(τi) eine Periodizität von p_l, wie weiter unter gezeigt wird, auf. a'(τi+ p_l) = a'(τi) (13) According to equation (13), the time-shifted state vector a '(τi) has a periodicity of p _l , as further shown below. a '(τ i + p _l ) = a '(τi) (13)
[0041] Wirdder linke Term von Gleichung (13) in Gleichung (12) eingesetzt undanschließenddie Periodizität ndes Zustandsvektors a(τi)berücksichtigt,so kann vergleichsweise trivial gemäß Gleichung (14) die Periodizität des zeitlichverschobenen Zustandsvektor a'(τi) über dieZykluslängep_l nachgewiesen werden. a'(τi+ p_l) = a((τi + p_l)·n/p_l) = a(τi·n/p₁ + n) = = a(τi·n/p_l)= a'(τi) (14) If the left-hand term of equation (13) is inserted into equation (12) and then the periodicity n of the state vector a (τi) taken into account, then the periodicity of the time-shifted state vector a '(τi) can be calculated comparatively trivially according to equation (14) Cycle length p _{l are} detected. a '(τ i + p _l ) = a ((τi + p _l ) * N / p _l ) = a (τi · n / p ₁ + n) = = a (τi · n / p _l ) = a '(τi) (14)
[0042] Aufgrundder Periodizitätdes zeitlich verschobenen Zustandsvektors a'(τi) über dieZykluslängep_l ist zum Taktzyklus τil, der dem Modulus bei Divisiondes Taktzykluses τidurch den teilerfremden Faktor p_l entspricht,gemäß Gleichung(15) der zeitlich verschobene Zustandsvektor a'(τ)gleich groß wiezum Taktzyklus τi. a'(τil)= a'(τi|p_l) = a'(τi) (15) Due to the periodicity of the temporally shifted state vector a '(τi) over the cycle length p _l is the clock cycle τil, which corresponds to the modulus in dividing the clock cycle τi by the divisive factor p _l , according to equation (15), the time-shifted state vector a' ( τ) equal to the clock cycle τi. a '(τil) = a' (τi | p _l ) = a '(τi) (15)
[0043] Dawie oben schon gezeigt alle Zustandsvektoren a(τi) innerhalb einer Zykluslänge n derbinärenZufallsfolge s(τi)nur ein einziges mal vorkommen und die zeitlich verschobenen Zustandsvektorena'(τil) = a'(τi) eine Teilmenge der Zustandsvektorena(τi) darstellen,kommen letztere auch nur ein einziges mal innrhalb der Zykluslänge n vor.Berücksichtigtman zusätzlich,daß jederzeitlich verschobene Zustandsvektor a'(τil)auf genau einen einzigen bestimmten Taktzyklus τil zurückgeht, kann für jedenzeitlich verschobenen Zustandsvektor a'(τil)eindeutig ein einziger zugehörigerTaktzyklus τilzugewiesen werden.ThereAs already shown above, all state vectors a (τi) within a cycle length n ofbinaryRandom sequence s (τi)occur only once and the temporally shifted state vectorsa '(τil) = a' (τi) is a subset of the state vectorsrepresent a (τi),The latter occur only once within the cycle length n.Consideredin addition,that everybodytime-shifted state vector a '(τil)can go back to exactly a single specific clock cycle τil, for eachtime-shifted state vector a '(τil)clearly a single associatedClock cycle τilbe assigned to.
[0044] Nachdem chinesischen Restklassensatz kann schließlich bei Kenntnis aller Moduluswerte τil, welche ausder Division des Taktzykluses τimit allen teilerfremden Faktoren p_l derSequenzklängen entstehen, eindeutig ein einziger zugehöriger Taktzyklus τi ermitteltwerden.After the Chinese residual class theorem, finally, knowing all the modulus values τil, which result from the division of the clock cycle τi with all the non-divisive factors p _{l of} the sequence sounds n, clearly a single associated clock cycle τi can be determined.
[0045] Somitist ein erfindungsgemäßes Verfahrengegeben, mit dem fürjeden teilerfremden Faktor p_l der Zykluslänge n einzum Meßtaktzyklus τx ausgelesenerZustandsvektor a(τx)jeweils ein zeitlich verschobener Zustandsvektor a'(τx) = a(τx·n/p_l)ermittelbar ist, welcher nur noch mit insgesamt p_l verschiedenen,zeitlich verschobenen Vergleichszustandsvektoren a_REF'(τil) auf Identität verglichenwerden muß.Ist fürjeden teilerfremden Faktor p_l ein zum ausgelesenenund zeitlich verschobenen Zustandsvektor a'(τx)identischer Vergleichszustandsvektor a_REF'(τxl) gefunden, so kann, wie obenausgeführt,eindeutig ein zugehörigerTaktzyklus τxlangegebenen werden. Aus allen fürjeden teilerfremden Faktor p_l auf dieseWeise ermittelten Taktzyklen τxlkann, wie weiter unten gezeigt, der gesuchte zum ausgelesenen Zustandsvektora(τx) gehörige Taktzyklus τx ermitteltwerden.Thus, a method according to the invention is provided with which for each non-divisive factor p _{l of} the cycle length n a state vector a (τx) read out for the measuring clock cycle τx, a time-shifted state vector a '(τx) = a (τx * n / p _l ) can be determined which only has to be compared with a total of p _l different time-shifted comparison state vectors a _REF '(τil) for identity. If a comparison state vector a _REF '(τxl) identical to the read-out and time-shifted state vector a' (τx) is found for each divisive factor p _l , then, as stated above, an associated clock cycle τxl can be unambiguously specified. As is shown below, the clock cycle τx belonging to the read-out state vector a (τx) can be determined from all clock cycles τxl determined in this way for each divisive factor p _l .
[0046] Derzeitlich verschobene Zustandsvektors a'(τx)= a(τx·n/p_l) kann aus Gleichung (7) gewonnen werden,indem die Laufvariable i "Null" gesetzt wird unddie Meßvariablex mit dem Faktor n/p_l multipliziert wird. AusGleichung (9) in Kombination mit Gleichung (10) ergibt sich somitGleichung (16) a'(τx) = a(τx·n/p_l))= V^x·n/pl·a(0) == K^n/pl·a(0) (16) The time-shifted state vector a '(τx) = a (τx * n / p _l ) can be obtained from equation (7) by setting the run variable i "zero" and multiplying the measurement variable x by the factor n / p _l , Equation (9) in combination with equation (10) thus gives equation (16) a '(τx) = a (τx · n / p _l ) = V ^{x · s / pl} · A (0) = = K ^{n / pl} · A (0) (16)
[0047] ZurBestimmung der in Gleichung (16) benötigten Koeffizienten der SubstitutionsmatrixK wird das Schieberegister 4 zum Starttaktzyklus τ0 = 0 miteinem Startzustandsvektor a(0) gemäß Gleichung (17) belegt: a(0) = (1, 0, .., 0) (17) To determine the coefficients of the substitution matrix K required in equation (16), the shift register 4 to the start clock cycle τ0 = 0 with a start state vector a (0) according to equation (17): a (0) = (1, 0, .., 0) (17)
[0048] Mitder Belegung des Startzustandsvektors a(0) gemäß Gleichung (17) ergibt sichder erste Spaltenvektor k₁ der SubstitutionsmatrixK bei zum Meßtaktzyklus τx eingelesenenZustandsvektor a(τx)unter Anwendung von Gleichung (7) in Kombination mit Gleichung (8)vergleichsweise trivial gemäß der Beziehungin Gleichung (18) k₁ = a(τx) (18) With the assignment of the start state vector a (0) according to equation (17), the first column vector k _{1 of} the substitution matrix K results in a relatively trivial state vector a (τx) read in for the measurement clock cycle τx using equation (7) in combination with equation (8) according to the relationship in equation (18) k ₁ = a (τx) (18)
[0049] Mitdem ermittelten ersten Spaltenvektor k₁ derSubstitutionsmatrix K kann der zweite Spaltenvektor k₂ derSubstitutionsmatrix K unter Anwendung von Gleichung (7) in Kombinationmit Gleichung (8) gemäß Gleichung(19) ermittelt werden. k₂ = a(τ(x+ 1)) + k₁·a₁(τ1) (19) With the determined first column vector k _{1 of} the substitution matrix K, the second column vector k _{2 of} the substitution matrix K can be determined using equation (7) in combination with equation (8) according to equation (19). k ₂ = a (τ (x + 1)) + k ₁ · a ₁ (τ1) (19)
[0050] Hierbeiwird die Tatsache ausgenutzt, daß zum Taktzyklus τ1 einzigdie Binärzustände a₁(τ1)und a₂(τ1) derersten und zweiten Schieberegisterstufe 5₁ und 5₂ einen von Null verschiedenen Wertaufweisen. Die hierzu benötigtenZustandsvektoren a(τ₁) und a(τ(x+ 1)) könnenaus dem Startzustandsvektor a(τ0= 0) und dem zum Meßtaktzyklus τx ausgelesenenZustandsvektor a(τx)unter Anwendung der mathematischen Beziehung in Gleichung (2) für die Binärzustände jedereinzelnen Schieberegisterstufe oder alternativ durch Anwendung vonGleichung (5) und (6) fürdie Binärzustände allerSchieberegisterzustufen insgesamt berechnet werden.Here, the fact is exploited that the clock cycle τ1 only the binary states a ₁ (τ1) and a ₂ (τ1) of the first and second shift register stage 5 ₁ and 5 ₂ have a value other than zero. The required state vectors a (τ ₁ ) and a (τ (x + 1)) can be obtained from the start state vector a (τ0 = 0) and the state vector a (τx) read out to the measure clock cycle τx using the mathematical relationship in equation (2). for the binary states of each shift register stage or, alternatively, by applying equations (5) and (6) for the binary states of all the shift register stages as a whole.
[0051] Ganzanalog werden die übrigenSpaltenvektoren k₃ bis k_m derSubstitutionsmatrix K ermittelt. Diese werden sukzessive beginnendmit dem Spaltenvektor k₃ und endend mitdem Spaltenvektor k_m gemäß Gleichung (20) berechnet:
[0052] Auchhier wird die Tatsache ausgenutzt, daß für die Berechnung des Spaltenvektorsk_i der Substitutionsmatrix K zum Taktzyklus τ(i – 1) einzigdie Binärzustände a₁(τ(i – 1)) bisa_i–1(τ(i – 1)) derersten bis i–1-ten Schieberegisterstufe 5₁ bis 5_i–1 einenvon Null verschiedenen Wert aufweisen Die Zustansvektoren a(τ3) bis a(τ(m – 1)) sowiea(τ(x +2)) bis a(τ(x+ m – 1))werden aus den bereits berechneten Zustandsvektoren a(τ1) und a(τ(x + 1))durch sukzessive Anwendung der mathematischen Beziehung in Gleichung(2) fürdie Binärzustände jedereinzelnen Schieberegisterstufe oder alternativ durch Anwendung vonGleichung (6) fürdie Binärzustände allerSchieberegisterzustufen berechnet.Here, too, the fact is exploited that only the binary states a ₁ (τ (i-1)) to a _i-1 (τ (i _-1 ) are used for calculating the column vector k _{i of} the substitution matrix K for the clock cycle τ (i-1) )) of the first to i-th shift register stages 5 ₁ to 5 _i-1 have a non-zero value The vectors of the vectors a (τ3) to a (τ (m-1)) as well as a (τ (x + 2)) to a (τ (x + m-1)) become from the already calculated state vectors a (τ1) and a (τ (x + 1)) by successively applying the mathematical relationship in equation (2) for the binary states of each shift register stage, or alternatively by applying equation (6) for the binary states of all the shift register stages.
[0053] Mitdern auf diese Weise ermittelten Spaltenvektoren k_i istdie Substitutionsmatrix K aufzubauen, welche im nächsten Schritteiner Matrizenmultiplikation um den Faktor n/p_l zurBildung der Matrix
[0054] DerFaktor c_li kann in Abhängigkeit der Existenz des zugehörigen Zweierexponenten 2ⁱ den Wert "0" oder "1" annehmen. Die Matrix
[0055] Aufdiese Weise muß dieMatrix
[0056] Mitder überdie Beziehung in Gleichung (22) ermittelten Matrix
[0057] DurchVergleich aller zu den einzelnen teilerfremden Faktoren p_l gehörigenzeitlich verschobenen Zustandsvektoren a'(τx)mit allen möglichenVergleichszustandsvektoren a_REF'(τil) und auftretender Identität zwischendem Zustandsvektor a'(τx) und einemder Vergleichszustandsvektoren a_REF'(τxl) können die zu den einzelen teilerfremdenFaktoren p_l gehörigen Taktzyklen τxl ermitteltwerden.By comparing all time-shifted state vectors a '(τx) belonging to the individual divisive factors p _l with all possible comparison state vectors a _REF ' (τil) and identity occurring between the state vector a '(τx) and one of the comparison state vectors a _REF ' (τxl) the clock cycles τxl belonging to the individual divisive factors p ₁ can be determined.
[0058] DerVergleichszustandsvektor a_REF'(τil) zum Taktzyklus τil kann für jedenteilerfremden Faktor p_l ausgehend von a_REF'(τil = (0)= a'(0) = a(0) unterAnwendung von Gleichung (16) mittels Substitution der Meßvariablex durch die Laufvariable i entsprechend Gleichung (23) vorab berechnetund anschließendin einem Speicher (11) abgelegt werden: a_REF'(τil) = a_REF'(τ(i·n/p_l))= V^i·n/pl·a_REF'(τil = 0) (23) The comparison state vector a _REF '(τil) at the clock cycle τil can be calculated for each non-alien factor p _l from a _REF ' (τil = (0) = a '(0) = a (0) using equation (16) by substitution of Measuring variable x calculated in advance by the running variable i according to equation (23) and then in a memory ( 11 ) are stored: a _REF '(τil) = a _REF '(Τ (i * n / p _l ) = V ^{i * n / pl} · a _REF '(τil = 0) (23)
[0059] Ineiner ersten Ausführungsformdes erfindungsgemäßen Verfahrenswerden im Rahmen einer Online-Lösungdie Vergleichszustandsvektoren a_REF'(τ(i + 1)l) zum Taktzyklus τ(i + 1)lfür jedenteilerfremden Faktor p_l gemäß Gleichung(24) iterativ aus einem Vergleichszustandsvektor a_REF'(τil) zum Taktzyklus τil berechnet undunmittelbar mit dem ausgelesenen und zeitlich verschobenen Zustandsvektora'(τx) verglichen.Der Vergleichszustandsvektor a_REF'(τ(i + 1)l) zum nächst höheren Taktzyklus τ(i + 1)linnerhalb der reduziert zu betrachtenden Taktzyklen τil ergibtsich füralle Laufvariablen i von 1 bis p_l – 1, wieaus Gleichung (23) leicht zu erkennen ist, gemäß Gleichung (24) durch Iterationaus dem Vergleichszustandsvektor a_REF'(τil) zum vorherigen Taktzyklus τil:
[0060] Eineiterative Bereichnung eines weiteren Vergleichszustandsvektor a_REF'(τ(i + 2)l)unterbleibt, sobald Identitätzwischen dem eingelesenen, zeitverschobenen Zustandsvektor a'(τ) und dem zu vergleichendenVergleichszustandsvektor a_REF'(τ(i + 1)l) besteht.An iterative enrichment of a further comparison state vector a _REF '(τ (i + 2) 1) is omitted as soon as identity between the read-in, time-shifted state vector a' (τ) and the comparison state vector a _REF '(τ (i + 1) 1) to be compared consists.
[0061] Nebendieser Online-Lösungwird in einer zweiten Ausführungsformdes erfindungsgemäßen Verfahrensim Rahmen einer Offline-Lösungder eingelesene, zeitlich verschobene Zustandsvektor a'(τx) mit sämtlichen vorab berechnetenund abgespeicherten Vergleichszustandsvektoren a_REF'(τil), welche gemäß Gleichung (23)für jedenteilerfremden Faktor p_l berechnet werden,verglichen.In addition to this online solution, in a second embodiment of the method according to the invention, the read in, time-shifted state vector a '(τx) with all previously calculated and stored comparison state vectors a _REF ' (τil), which according to equation (23) for each non-divisive factor p _l are compared.
[0062] DerVorteil der Online-Lösunggegenüberder Offline-Lösungliegt darin, daß dieiterative Berechnung der Vergleichszustandsvektoren a_REF'(τil) abgebrochen werden kann,sobald ein zum ausgelesenen und zeitlich verschobenen Zustandsvektora'(τx) passenderVergleichszustandsvektor a_REF'(τil) gefunden ist. Der Rechenaufwandkann sich folglich bei der ersten Ausführungsform gegenüber demRechenaufwand der zweiten Ausführungsformdeutlich minimieren.The advantage of the online solution over the offline solution is that the iterative calculation of the comparison state vectors a _REF '(τil) can be aborted as soon as a read to the read and time-shifted state vector a' (τx) matching state comparison vector a _REF '(τil ) is found. The computational effort can thus be significantly reduced in the first embodiment compared to the computational effort of the second embodiment.
[0063] Istder teilerfremde Faktor p_l vergleichsweisegroß,so ist der ausgelesene und zeitlich verschobene Zustandsvektor a'(τx) mit einer Vielzahl von Vergleichszustandsvektorena_REF'(τil) – nämlich insgesamtp_l Vergleichszustandsvektoren a_REF'(τil) – zu vergleichen. Um den Berechnungsaufwandder Vergleichszustandsvektoren a_REF'(τil) zu reduzieren, wird nureine Teilmenge a_REF''(τil) der insgesamtp_l Vergleichszustandsvektoren a_REF'(τil) – i.a. nur die Vergleichszustandsvektorena_REF'(τil) zu denersten o Taktzyklen der reduzierten, insgesamt p_l Takltzyklenenthaltenden Taktzyklensequenz τil – gemäß Gleichung(25) berechnet und in einem Speicher (11) abgelegt.
[0064] Wirdin einem ersten Vergleichszyklus des eingelesenen und zeitlich verschobenenZustandsvektors a(τx)mit der Teilmenge a_REF''(τil) der Vergleichszustandsvektorena_REF'(τil) keineIdentitätzwischen dem eingelesenen und zeitlich verschobenen Zustandsvektora(τx) undeinem der Zustandsvektoren der Teilmenge a_REF''(τil') der Vergleichszustandsvektorena_REF'(τil) ermittelt,so wird anstelle einer erneuten Berechnung einer weiteren Teilmengea_REF'''(τil)der Vergleichszustandsvektoren a_REF'(τil) und eines Vergleichs deseingelesenen und zeitlich verschobenen Zustandsvektors a(τx) mit dererneut berechneten Teilmenge a_REF'''(τil) der Vergleichszustandsvektorena_REF'(τil) der eingeleseneund zeitlich verschobene Zustandsvektor a(τx) um insgesamt o·n/p_l Taktzyklen gemäß Gleichung (26) zeitlich verschoben,um auf diese Weise die Zustandsvektoren a''(τx) zu denden eingelesenen und zeitlich verschobenen Taktzyklen τx zeitlichnachfolgenden Taktzyklen mit der Teilmenge a_REF''(τil)der Vergleichszustandsvektoren a_REF'(τil) zu vergleichen.
[0065] Derum insgesamt o·n/p_l Taktzyklen zeitlich verschobene eingeleseneZustandsvektor a''(τx) wird nun ebenfalls mit derTeilmenge a_REF''(τil) der Vergleichszustandsvektorena_REF'(τil) auf Identität überprüft. Wird abermalskeine Identitätzwischen eingelesenen und zeitlich verschobenen Zustandsvektor a''(τx)und der Teilmenge a_REF''(τil)) derVergleichszustandsvektoren a_REF'(τil) festgestellt, so wird dereingelesene und zeitlich verschobene Zustandsvektor sooft auf dieseWeise zeitlich verschoben und mit der Teilmenge a_REF''(τil)der Vergleichszustandsvektoren a_REF'(τil) verglichen, bis ein zumeingelesenen und zeitlich verschobenen Zustandsvektor a''(τx)passender Vergleichszustandsvektor in der Teilmenge a_REF''(τil)der Vergleichszustandsvektoren a_REF'(τil) gefunden ist. Der in derTeilmenge a_REF''(τil) der Vergleichszustandsvektorena_REF'(τil) zum eingelesenenund w-fach zeitlich verschobenen Zustandsvektor a''(τx)passende Vergleichszustandsvektor a_REF''(τxl') liefert den zugehörigen Taktzyklus τxl'. Der zum teilerfremdenFaktor p_l gehörige gesuchte Taktzyklus τxl ergibt sichsomit gemäß Gleichung(27): τxl = τxl' + w·o (27) The read-in state vector a "(τx), which is shifted in time by a total of 0 · n / p _l clock cycles, is then likewise checked for identity with the subset a _REF " (τil) of the comparison state vectors a _REF '(τil). If no identity is again detected between read-in and time-shifted state vector a '' (τx) and the subset a _REF '' (τil) of the comparison state vectors a _REF '(τil), then the read-in and time-shifted state vector becomes time-like in this way shifted and compared with the subset a _REF '' (τil) of the comparison state vectors a _REF '(τil) until a read state of the vector read and temporally shifted state vector a''(τx) matching state vector in the subset a _REF ''(τil) of the comparison state vectors a _REF '(τil) is found. The comparison state vector a _REF '' (τxl ') which is appropriate in the subset a _REF ''(τil) of the comparison state vectors a _REF ' (τil) for the read in and time-shifted state vector a '' (τx) supplies the associated clock cycle τxl ' , The desired clock cycle τx1 belonging to the divisive factor p ₁ thus results according to equation (27): τxl = τxl '+ w · o (27)
[0066] DieErmittlung des gesuchten Taktzykluses τx aus allen zu den teilerfremdenFaktoren p_l gehörigen Taktzyklen τxl, die jeweilsdem Moduluswert τx|p_l der Division des gesuchten Taktzykluses τx durch denteilerfremden Faktor p_l entsprechen, wirdim folgenden aufgezeigt.The determination of the desired clock cycle τx from all of the non-divisive factors p _l associated clock cycles τxl corresponding respectively to the modulus τx | p _{l of} the division of the sought clock cycle τx by the divisive factor p _{l is shown} below.
[0067] Während imbisherigen Abschnitt des erfindungsgemäßen Verfahrens die Moduluswerte τxl des gesuchtenTaktzykluses τxaus der Faktorzerlegung der Zykluslänge n in ihre insgesamt u teilerfremdenFaktoren p_l hervorgehen, ist im nun folgendenAbschnitt des erfindungsgemäßen Verfahrensder inverse Verfahrensweg zu beschreiten, indem ausgehend von einemteilerfremden Startfaktor p₁ sukzessivealle übrigenu – 1teilerfremden Faktoren p_l hinzumultipliziertwerden, bis sich nach insgesamt u – 1 Mulitiplikationen aller übrigen u – 1 teilerfremdenFaktoren die Zykluslängen wieder ergibt. Gemäß Gleichung(28) erhältder teilerfremde Startfaktor fürdie "rückwärts laufendeIteration", demder teilerfremde Faktor p₁ zugewiesen wird,den Index u + 1: p_u+1 = p₁ (28) While in the previous section of the method according to the invention the modulus values τxl of the clock cycle τx sought result from the factorization of the cycle length n into their overall non-divisive factors p ₁ , in the following section of the method according to the invention the inverse process path is to be taken, starting from a non-divisional starting factor p _1, all other u - 1 divisive factors p _{l are} successively multiplied until, after a total of u - 1 multiplications of all the other u - 1 divisive factors, the cycle length n results again. According to equation (28), the non-divisional starting factor for the "backward iteration" to which the divisive factor p _{1 is} assigned receives the index u + 1: p _{u + 1} = p ₁ (28)
[0068] DieZwischenprodukte p_u+v der sukzessiven Multiplikationenergeben sich gemäß Gleichung(29):
[0069] DasZwischenprodukt p_u+v in Gleichung (29) kannauch als Iteration aus dem vorherigen Zwischenprodukt p_u+v–1 gemäß Gleichung(30) analog dargestellt werden: p_u+v = p_u+v–1·p_v (30) The intermediate product p _{u + v} in equation (29) can also be represented analogously as an iteration from the previous intermediate product p _{u + v-1} according to equation (30): p _{u + v} = p _{u + v 1} · p _v (30)
[0070] Für jedendieser Zwischenprodukte p_u+v der teilerfremdenFaktoren p_l wird der korrespondierende Moduluswert τ(u + v) = τx|p_u+v ermittelt, bis nach insgesamt u – 1 Iterationsschrittender zum Endprodukt p_2u = n korrespondierendeModuluswert τ_2u mit dem gesuchten Taktzyklus τx konvergiert.For each of these intermediate products p _{u + v of} the non-divisive factors p _l , the corresponding modulus value τ (u + v) = τx | p _{u + v is} determined until, after a total of u-1 iteration steps, the modulus value τ _2u corresponding to the final product p _2u = n converges with the desired clock cycle τx.
[0071] Diezu den Zwischenprodukten p_u+v gehörigen Moduluswerte τ(u + v) können iterativermittelt werden, indem fürdie Iterationsschritte u + v, u + v – 1 und v der Gleichung (30)der gesuchte Taktzyklus τxjeweils – inverszur Modulusdivision – alsAddition des Modulus und des Produkts aus Divisor und Dividend derModulusdivision in der Dreifachgleichung (31) dargestellt wird: τx = τ(u + v) + k·p_u+v = τ(u + v – 1) + f·p_u+v–1 == τ(v) +e·p_v (31) The modulus values τ (u + v) belonging to the intermediate products p _{u + v} can be determined iteratively, for the iteration steps u + v, u + v-1 and v of equation (30), the sought clock cycle τx respectively - inverse to the modulus division Is represented as the addition of the modulus and the product of divisor and dividend of the modulus division in the triple equation (31): τx = τ (u + v) + k · p _{u + v} = τ (u + v-1) + fp _{u + v 1} = = τ (v) + e · p _v (31)
[0072] Dieganzzahligen Faktoren k, e und f stellen die Dividenden der jeweiligenModulusdivisionen dar.Theinteger factors k, e and f represent the dividends of the respectiveModulus divisions.
[0073] ZurErmittlung der Iterationsformel für die Berechnung des Moduluswertes τ(u + v) ausdem Moduluswert τ(u+ v – 1)wird die linke und halblinke mathematische Beziehung der Dreifachgleichung(31) herangezogen und gemäß Gleichung(31) unter Anwendung von Gleichung (30) umgeformt: τ(u + v) = τ(u + v – 1) + f·p_u+v–1 – k·p_u+v = = τ(u+ v – 1)+ (f – k·p_u)·p_u+v–1 (32) In order to determine the iteration formula for the calculation of the modulus value τ (u + v) from the modulus value τ (u + v-1), the left-hand and half-blind mathematical relationship of the triple equation (31) is used and according to equation (31) using equation (31). 30) transformed: τ (u + v) = τ (u + v-1) + fp _{u + v 1} - k · p _{u + v} = = τ (u + v - 1) + (f - k · p _u ) · P _{u + v 1} (32)
[0074] Für die Bestimmungdes Faktors k und fürdie Überführung desTerms k·p_u in einen für eine Iterationsformel geeignetenTerm, der lediglich von den Faktoren τ(u + v), τ(u + v – 1) und/oder p_u+v–1 abhängig ist,wird gemäß Gleichung(33) eine Differenzgröße d zwischenden bekannten Moduluswerten τ(v)und τ(u+ v – 1)eingeführt,in der die mathematische Beziehung der rechten und halbrechten Seiteder Dreifachgleichung (31) benutzt wird: d = τ (u+ v – 1) – τ(v) = f·p_u+v–1 +e·P_v (33) For the determination of the factor k and for the transformation of the term k · p _u into a term suitable for an iterative formula, which is only dependent on the factors τ (u + v), τ (u + v-1) and / or p _{u + v-1} , a difference quantity d between the known modulus values τ (v) and τ (u + v-1) is introduced according to equation (33) using the mathematical relationship of the right and half-right sides of the triple equation (31) becomes: d = τ (u + v-1) -τ (v) = f * p _{u + v 1} + e · P _v (33)
[0075] Gleichung(33) weist die zwei Unbekannten e und f auf. In einem ersten Lösungsschrittwerden jeweils die unbekannten Faktoren e bzw. f in Abhängigkeitder bekannten Differenzgröße d ermittelt.Hierzu wird eine Gleichung (34) konstruiert, die ebenfalls wie dierechte Seite der Gleichung (33) eine summarische Zerlegung der teilerfremdenFaktoren p_v und p_u+v–1 enthält. Diesummarische Zerlegung der teilerfremden Faktoren p_v und p_u+v–1 inGleichung (34) ergibt genau den Wert "1",um einen Koeffizientenvergleich zwischen der summarischen Zerlegungder teilerfremden Faktoren p_v und p_u+v–1 gemäß Gleichung(35) durchführenzu können: y·p_v – z·p_u+v–1 =1 (34) d = d·(y·p_v – z·p_u+v–1)= d·y·p_v – d·z·p_u+v–1 =e·p_v + f·p_u+v–1 (35) Equation (33) has the two unknowns e and f. In a first solution step, the unknown factors e and f are respectively determined as a function of the known difference quantity d. For this purpose, an equation (34) is constructed which, like the right-hand side of equation (33), also contains a summary decomposition of the non-prime factors p _v and p _{u + v-1} . The summary decomposition of the non-prime factors p _v and p _{u + v-1} into equation (34) gives exactly the value "1" to obtain a coefficient comparison between the summation of the non-prime factors p _v and p _{u + v-1} according to Equation (34). 35): y · p _v - z · p _{u + v 1} = 1 (34) d = d · (y · p _v - z · p _{u + v 1} ) = d · y · p _v - d · z · p _{u + v 1} = e · p _v + f · p _{u + v 1} (35)
[0076] DerKoeffizientenvergleich ergibt, daß der Faktor e dem Produktd·y undder Faktor f dem Produkt d·z entspricht.Of theCoefficient comparison reveals that the factor e is the productd · y andthe factor f corresponds to the product dz.
[0077] DurchBestimmung der Unbekannten y und z in Gleichung (34) kann jeweilsdie Unbekannte e bzw. f ermittelt werden. Da nur ein einziges ganzzahligesUnbekannten-Paar (y; z) Gleichung (34) erfüllen kann, kann dieses durchsukzessives Inkrementieren oder Dekrementieren ermittelt werden.Der möglicheWertebereich der Unbekannten y liegt im Intervall –p_u+v–1 < y < p_u+v–1,der möglicheWertebereich der Unbekannten z liegt im Intervall – p_v < z < p_v.By determining the unknowns y and z in equation (34), the unknowns e and f can be determined in each case. Since only a single integer unknown pair (y; z) can satisfy equation (34), this can be determined by successive incrementing or decrementing. The possible value range of the unknown y lies in the interval -p _{u + v-1} <y <p _{u + v-1} , the possible value range of the unknown z lies in the interval - p _v <z <p _v .
[0078] Mitder mittels Gleichung (34) iterativ ermittelten Unbekannten z kannGleichung (32) unter Anwendung der linken Gleichungsbeziehung vonDoppelgleichung (33) und Einführungeines weiteren ganzzahligen Faktors ε = k/z in Gleichung (36) übergeführt werden. τ(u + v) = τ(u + v – 1) + (d – ε·p_u)·z·p_u+v–1 (36) Using the unknown z determined iteratively by equation (34), equation (32) can be converted to equation (36) using the left equation equation of double equation (33) and introducing another integer factor ε = k / z. τ (u + v) = τ (u + v - 1) + (d - ε · p _u ) * Z * p _{u + v 1} (36)
[0079] Führt manin Gleichung (36) den Moduluswert d_u derDivision der Differenzgröße d durchden teilerfremden Faktor p_u ein, so gehtGleichung (36) in Gleichung (37) über: τ(u+ v) = τ(u+ v – 1)+ du·z·p_u+v–1 (37) If we introduce in equation (36) the modulus value d _{u of} the division of the difference quantity d by the non-divisive factor p _u , then equation (36) goes into equation (37): τ (u + v) = τ (u + v - 1) + du · z · p _{u + v 1} (37)
[0080] Wirdin Gleichung (37) die Größe h = d_u·zeingeführt,so ergibt sich Gleichung (38) zur iterativen Berechnung der Taktzyklen τ(u + v),welche für τ(u + v) = τ2u zum gesuchtenTaktzyklus τxkonvergiert. τ(u + v) = τ(u + v – 1) + h·p_u+v–1 (38) If the quantity h = d _u * z is introduced in equation (37), then equation (38) results for the iterative calculation of the clock cycles τ (u + v), which converges for τ (u + v) = τ2u to the desired clock cycle τx , τ (u + v) = τ (u + v-1) + h * p _{u + v 1} (38)
[0081] Aufbauendauf den bisherigen Herleitungen der mathematischen Beziehungen werdendie drei Ausführungsformendes erfindungsgemäßen Verfahrenszur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen in einem binärenZufallsgenerator gemäß 2, 2A, 2B und 2C vorgestellt.Based on the previous derivations of the mathematical relationships, the three embodiments of the inventive method for determining the number Δτ of elapsed clock cycles in a binary random number generator according to 2 . 2A . 2 B and 2C presented.
[0082] Im übergeordnetenFlußdiagrammin 2, das füralle drei Ausführungsformendes erfindungsgemäßen VerfahrensGültigkeitbesitzt, werden in einem ersten Verfahrensschritt S10 die Binärzustände allerm Schieberegisterstufen zu einem Zeitpunkt t_x,der der Beginn t_l und/oder das Ende t2 deszu überwachenden Zeitintervalls Δt sein kann,eingelesen und einem Zustandsvektor a(τx) zugewiesen. Der Meßtaktzyklus τx ist derzum Zeitpunkt t_x gehörige Taktzyklus. Der Einfachheithalber wird im folgenden nicht mehr zwischen Beginn t₁ undEnde t₂ des zu überwachenden Zeitintervalls Δt unterschieden,sondern nur noch der allgemeine Meßzeitpunkt t_x undder dazugehörigeMeßtakzyklus τx verwendet.In the parent flowchart in 2 , which is valid for all three embodiments of the method according to the invention, in a first method step S10, the binary states of all m shift register stages at a time t _x , which may be the beginning t _l and / or the end t2 of the time interval .DELTA.t to be monitored, read and assigned to a state vector a (τx). The measuring clock cycle τx is the clock cycle associated with the time t _x . For the sake of simplicity, no distinction is made between the beginning t ₁ and the end t _{2 of} the time interval Δt to be monitored in the following, but only the general measurement time t _x and the associated Meßtakzyklus τx used.
[0083] ImnächstenVerfahrensschritt S20 werden die Koeffizienten der SubstitutionsmatrixK, die der x-fach multiplizierten Verschiebematrix V entspricht,berechnet. Die einzelnen Spaltenvektoren k₁ derSubstitutionsmatrix könnenentsprechend der Gleichungen (18), (19) und (20) – Gleichung(18) fürden Spaltenvektor k₁, Gleichung (19) für den Spaltenvektork₂ und Gleichung (20) für die Spaltenvektoren k₃ bis k_m – berechnetwerden. Hierbei handelt es sich um eine iterative Berechnung, sodaß für die Berechnungdes Spaltenvektor k_l alle in der SubstitutionsmatrixK links des Spaltenvektors k_l angeordnetenSpaltenvektoren k₁ bis k_l–1 invorherigen Iterationsschritten berechnet werden müssen. Dieinsbesondere in den Gleichungen (19) und (20) benötigten Zustandvektorena(τ(i -1)) und a(τ(x+ i – 1))für allei von 2 bis m könnenentweder getrennt fürjede einzelne Schieberegisterstufe mittels Gleichung (2) iterativaus den Zustandvektoren a(τx)und a(0) oder fürden gesamten Zustandsvektor mittels Gleichung (5) und (6) berechnetwerden.In the next method step S20, the coefficients of the substitution matrix K, which corresponds to the x-times multiplied displacement matrix V, are calculated. The individual column vectors k _{1 of} the substitution matrix can be calculated according to equations (18), (19) and (20) - equation (18) for the column vector k ₁ , equation (19) for the column vector k ₂ and equation (20) for the column vectors k ₃ to k _m - be calculated. This is an iterative calculation such that k for calculation of the column vector _l in all the substitution matrix K to the left of the column vector k _l disposed column vectors k ₁ to k _L-1 need to be computed in the previous iteration steps. The state vectors a (τ (i-1)) and a (τ (x + i-1)) required in particular in equations (19) and (20) for all i from 2 to m can either be used separately for each individual shift register stage Equation (2) can be calculated iteratively from the state vectors a (τx) and a (0) or for the entire state vector by means of equations (5) and (6).
[0084] ImnächstenVerfahrensschritt S30 wird fürjeden teilerfremden Faktor p_l der Zykluslänge n diejeweilige Matrix
[0085] DieMatrizen
[0086] ImnächstenVerfahrensschritt S40 erfolgt der Vergleich des eingelesenen, umden Faktor n/p_l jeweils zeitlich verschobenenZustandsvektors a'(τx) mit jeweilsinsgesamt p_l um den Faktor n/p_l zeitlichverschobenen Vergleichszustandsvektoren a_REF'(τil). Da die Ermittlung der Vergleichszustandsvektorena_REF'(τil) wie auchdie Art des Vergleichs zwischen dem eingelesenen, zeitlich verschobenenZustandsvektor a'(τx) und denjeweils zu untersuchenden Vergleichszustandsvektoren a_REF'(τil) zwischen den einzelnen Ausführungsformenunterschiedlich ist, wird auf die Beschreibung des zu den drei Ausführungsformenpassenden Verfahrensschritt S40 weiter unten verwiesen. Ergebnisdes Verfahrensschritts S40 ist bei allen drei Ausführungsformenein zum eingelesenen, zeitlich verschobenen Zustandsvektor a'(τx) passender zeitlich verschobenerVergleichszustandsvektor a_REF'(τil) für jeden teilerfremden Faktorp_l.In the next step S40, the comparison of the read-in, by the factor n / p _l time shifted each state vector a 'occurs (τx), each with a total of p _l by the factor n / p _l time-shifted comparison state vector a _REF' (τil). Since the determination of the comparison state vectors a _REF '(τil) as well as the type of comparison between the read-in, time-shifted state vector a' (τx) and the respectively to be examined comparison state vectors a _REF '(τil) between the individual embodiments is different, is on the description of the matching to the three embodiments method step S40 further down. The result of method step S40 in all three embodiments is a time-shifted comparison state vector a _REF '(τil) suitable for the read-in, time-shifted state vector a' (τx) for each non-divisive factor p _l .
[0087] ImnächstenVerfahrensschritt S50 werden die zu den gefundenen Vergleichszustandsvektoren a_REF'(τil) eindeutiggehörendenTaktzyklen τxlfür jedender insgesamt j teilerfremden Faktor p_l ausdem Speicher ausgelesen.In the next method step S50, the clock cycles τxl uniquely associated with the found comparison state vectors a _REF '(τil) are read from the memory for each of the total non-divisive factors p _l .
[0088] ImabschließendenVerfahrensschritt S60 werden alle zu den insgesamt j teilerfremdenFaktoren p_l jeweils ermittelten Taktzyklen τxl, die Moduluswerteder Division des gesuchten Taktzyklus τx durch den jeweiligen teilerfremdenFaktor p_l darstellen, zur iterativen Berechnungdes gesuchten Taktzykluses gemäß Gleichung(38) verwendet. Die hierbei benötigtenZwischenprodukte p_u+v–1 der teilerfremdenFaktoren p_l werden entsprechend Gleichung(29) iterativ aus dem jeweiligen vorhergehenden Zwischenproduktp_u+v–2 unddem jeweiligen teilerfremden Faktor p_v berechnet.Der unbekannte Faktor z kann in Kombination mit dem ebenfalls unbekanntenFaktor y bei bekannten teilerfremden Faktor p_v undbekannten Zwischenprodukt p_u+v–1 durch iteratives Inkrementierenoder Dekrementieren zur Erfüllungvon Gleichung (34) ermittelt werden. Schließlich kann der unbekannte Moduluswertd_u bei Division der Differenzgröße d durchden teilerfremden Faktor p_u auch ermitteltwerden, da die Differenzgröße d gemäß Gleichung(33) aus den bekannten Taktzyklen τ_u+v–1 und τ_v hervorgeht.In the final process step S60 all the total j prime factors p _l respectively determined clock cycles τxl, the modulus values of the sought clock cycle Division τx _l represented by the respective prime factor p, equation (38) used for the iterative computation of the required clock cycle according to. The intermediates p _{u + v-1 of} the non-divisive factors p _l required in this case are calculated iteratively from the respective preceding intermediate product p _{u + v-2} and the respective non-divisive factor p _{v in} accordance with equation (29). The unknown factor z can be determined in combination with the also unknown factor y for known non-divisive factor p _v and known intermediate product p _{u + v-1} by iterative incrementing or decrementing to satisfy equation (34). Finally, the unknown modulus value d _u can also be determined by dividing the difference quantity d by the non-divisive factor p _u , since the difference quantity d according to equation (33) results from the known clock cycles τ _{u + v-1} and τ _v .
[0089] Umdie Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators zu ermitteln, wird der für den Startzeitpunkt t₁ gehörigeTaktzyklus τ1und der fürden Endezeitpunkt t₂ gehörige Taktzyklus τ2 des zu messendenZeitintervalls Δtgemäß dem in 2 dargestelltenerfindungsgemäßen Verfahrenermittelt und die Anzahl der Taktzyklen Δτ von abgelaufenenen Taktzyklengemäß Gleichung(39) aus der Differenz von τ1und τ2 berechnet: Δτ = τ2 – τ1 (39) In order to determine the number Δτ of elapsed clock cycles of a binary random number generator, the clock cycle τ1 associated with the start time t ₁ and the clock cycle τ ₂ associated with the end time t ₂ of the time interval Δt to be measured is determined according to the 2 determined inventive method and the number of clock cycles .DELTA..tau. of elapsed clock cycles according to equation (39) calculated from the difference of τ1 and τ2: Δτ = τ 2 -τ 1 (39)
[0090] Wirdals Startzeitpunkt die Initialisierung des binären Zufallsgenerators gewählt, soist der Taktzyklus τ1in Gleichung (39) mit dem Wert "0" zu belegen.Becomesas the start time, the initialization of the binary random generator selected, sois the clock cycle τ1in equation (39) with the value "0".
[0091] DerVerfahrensschritt S40 gliedert sich bei der ersten in 2A gezeigtenAusführungsformdes erfindungsgemäßen Verfahrensin einen ersten Unterverfahrensschritt S40B1, in dem für jedenteilerfremden Faktor p_l auf der Basis derVerschiebematrix V nach Gleichung (6) die modifizierte Verschiebematrix
[0092] Anschließend wirdsukzessive im Unterverfahrensschritt S40B2 für jeden teilerfremden Faktorp_l der zeitlich verschobene Vergleichszustandvektora_REF'(τil) zum Taktzyklus τil aus demVergleichszustandvektor a_REF'(i – 1)l) zumvorherigen Taktzyklus τ(i –1)l iterativgemäß Gleichung(24) ermittelt. Die Iteration beginnt jeweils beim Startvergleichzustandsvektora_REF'(0)= a(0).Is then successively in sub-step S40B2 for every prime factor p _l of the time-shifted comparison state vector a _REF '(τil) for clock cycle τil from the comparison state vector a _REF' (i - 1) l) for the previous clock cycle τ (i -1) l iteratively according Equation (24) is determined. The iteration begins at the start _{comparison state vector} a _REF '(0) = a (0).
[0093] Imdarauffolgenden Unterverfahrensschritt S40B3 wird der eingelesene,zeitlich verschobene Zustandsvektor a'(τx) jeweilsfür jedenteilerfremden Faktor p_l mit dem iterativermittelten Vergleichszustandsvektor a_REF'(τil) verglichen.In the subsequent sub-method step S40B3, the read in, time-shifted state vector a '(τx) is compared for each non-divisive factor p _l with the iteratively determined comparison state vector a _REF ' (τil).
[0094] Wirdim nächstenUnterverfahrensschritt S40B4 keine Identität zwischen dem eingelesenen,zeitlich verschobenen Zustandsvektor a'(τx)und dem jeweils fürjeden teilerfremden Faktor p_l iterativ ermitteltenVergleichszustandsvektor a_REF'(τil) festgestellt, so wird einfür denjeweiligen teilerfremden Faktor p_l gehöriger Vergleichszustandsvektora_REF'(τ(i + 1)l)zum nachfolgenden Taktzyklus τ(i+ 1)l gemäß Gleichung(24) berechnet und dem Vergleich mit dem eingelesenen, zeitlichverschobenen a'(τx) im UnterverfahrensschrittS40B3 zugeführt.Andernfalls ist der passende Vergleichszustandsvektor a_REF'(τxl) gefunden und das erfindungsgemäße Verfahrenwird mit Verfahrensschritt S50, wie weiter oben dargestellt, fortgesetzt.If, in the next sub-method step S40B4, no identity is found between the read-in, time-shifted state vector a '(τx) and the comparison state vector a _REF ' (τil) iteratively determined for each non-divisive factor p _l , then one belonging to the respective non-divisive factor p _l is determined Comparison state _vector a _REF '(τ (i + 1) l) to the subsequent clock cycle τ (i + 1) l calculated according to equation (24) and the comparison with the read, time shifted a' (τx) in the sub-process step S40B3 supplied. Otherwise, the appropriate comparison state vector a _REF '(τxl) is found and the method according to the invention is continued with method step S50, as described above.
[0095] Inder zweiten in 2B dargestellten Ausführungsformdes erfindungsgemäßen Verfahrenswird in einem Verfahrensschritt S00A im Offline-Betrieb, bevor daseigentliche erfinderische Verfahren zur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators mit Verfahrensschritt S10 begonnen wird, für jedenteilerfremden Faktor p_l und für jede Laufvariablei von 1 bis p_l – 1 jeweils die modifizierte VerschiebungsmatrixV^i·n/pl ausder ursprünglichenVerschiebematrix V gemäß Gleichung(6) durch Matrizenmultiplikation berechnet.In the second in 2 B In an embodiment of the method according to the invention, in a method step S00A in the offline mode, before the actual inventive method for determining the number Δτ of elapsed clock cycles of a binary random generator is started with method step S10, for each non-divisive factor p ₁ and for each variable i of FIG to p _l -1, respectively, the modified displacement matrix V ^{i * n / pl is} calculated from the original displacement matrix V according to equation (6) by matrix multiplication.
[0096] Imdarauffolgenden Verfahrensschritt S05B werden für jeden teilerfremden Faktorp_l jeweils alle p_l Vergleichszustandsvektorena_REF'(τil) mittelsder jeweiligen modifizierten Verschiebematrizen V^i·n/pl ausVerfahrensschritt S00B gemäß Gleichung(23) aus dem Startvergleichszustandsvektor a_REF'(0) = a(0) offlineberechnet.In the following step S05B are p _l in each case all p _l comparison state vector a _REF '(τil) by means of the respective modified Verschiebematrizen V ^{i · n / pl} from process step S00B in accordance with equation (23) from the start comparison state vector a _REF' (0) for each prime factor = a (0) calculated offline.
[0097] Imeigentlichen Verfahrensschritt S40B der zweiten Ausführungsformdes erfindungsgemäßen Verfahrenswird fürjeden teilerfremden Faktor p_l der jeweilsim Verfahrensschritt S30 ermittelte eingelesene, zeitlich verschobeneZustandsvektor a'(τx) mit jeweilsallen Vergleichszustandsvektoren a_REF'(τil) aus Verfahrensschritt S05Bauf Identitätverglichen. Wird hierbei ein passender Vergleichszustandsvektora_REF'(τxl) gefunden,so wird das Verfahren mit Verfahrensschritt S50, wie weiter obendargestellt, fortgesetzt.In the actual method step S40B of the second embodiment of the method according to the invention, the read-in, time-shifted state vector a '(τx) determined in step S30 is compared with each of all comparison state vectors a _REF ' (τil) from step S05B for identity for each non-divisive factor p _l . If in this case a suitable comparison state vector a _REF '(τxl) is found, the method is continued with method step S50, as described above.
[0098] Umden Such- bzw. Vergleichvorgang in Verfahrensschritt S40B zu beschleunigen,sind die in Verfahrensschritt S05B offline berechneten Vergleichszustandvektorena_REF'(τil) geeignetim Speicher abzulegen. Wird im Verfahrensschritt S40B ein binäres Suchverfahren über einenEntscheidungsbaum benutzt, so wird der eingelesene, zeitlich verschobeneZustandsvektor a'(τx) mit demVergleichszustandsvektor a_REF'(τil) nicht hinsichtlich allerKomponenten in einem einzigen Vergleichsschritt verglichen, sonderndie einzelnen Komponenten werden sequentiell miteinander verglichen.Auf diese Weise muß dereingelesene, zeitlich verschobene Zustandsvektor a'(τx) hinsichtlich der noch zuvergleichenden Komponenten nur noch mit Vergleichzustandsvektorena_REF'(τil) verglichenwerden, die in den bisher betrachteten Komponenten gleiche Binärwerte zumeingelesenen, zeitlich verschobenen Zustandsvektor a'(τx) aufweisen. Die dadurch realisierteReduzierung von Vergleichsoperationen bedingt eine Abspeicherungsreihenfolgeder Vergleichszustandsvektoren a_REF'(τil) im Verfahrensschritt S05B,in der die Vergleichszustansvektoren a_REF'(τil) entsprechend ihrer Komponentenbelegungin einer Entscheidungsbaumhierarchie angeordnet sind. Bei Anwendungeines Hash-Suchverfahrens im Verfahrensschritt S40B, bei dem zurBeschleunigung des Such- und Vergleichsprozesses nur bestimmte Komponentendes eingelesenen, zeitlich verschobenen Zustandsvektors a'(τx) und des Vergleichszustandsvektorsa_REF'(τil) miteinanderverglichenen werden, ist auch eine entsprechende Abspeicherungsreihenfolgeder Vergleichszustandsvektoren a_REF'(τil) im Verfahrensschritt S05Bvorzusehen.In order to accelerate the search or comparison process in method step S40B, the comparison state vectors a _REF '(τil) calculated offline in method step S05B are to be suitably stored in the memory. If a binary search method via a decision tree is used in method step S40B, the read in, time-shifted state vector a '(τx) is not compared with the comparison state vector a _REF ' (τil) with respect to all components in a single comparison step, but the individual components become sequential compared to each other. In this way, the read in, time-shifted state vector a '(τx) with respect to the still to be compared components only with comparison state vectors a _REF ' (τil) must be compared in the previously considered components equal binary values to the read, time-shifted state vector a ' (τx). The resulting reduction of comparison operations requires a storage order of the comparison state vectors a _REF '(τil) in step S05B, in which the comparison state vectors a _REF ' (τil) are arranged according to their component occupancy in a decision tree hierarchy. When applying a hash search method in method step S40B, in which only certain components of the read-in, time-shifted state vector a '(τx) and the comparison state vector a _REF ' (τil) are compared with one another to speed up the search and compare process, a corresponding one is also used Storage order of the comparison state vectors a _REF '(τil) to provide in step S05B.
[0099] Inder dritten in 2C dargestellten Ausführungsformdes erfindungsgemäßen Verfahrenswerden analog zur zweiten Ausführungsformin einem Verfahrensschritt S00C für teilerfremden Faktor p_l mit großen Werten insgesamt o verschiedenemodifizierte Verschiebematrizen
[0100] Imdarauffolgenden Verfahrensschritt S05C werden für teilerfremde Faktor p_l mit hohen Werten jeweils Untermengen a_REF''(τil) von jeweils insgesamt oVergleichszustandsvektoren a_REF'(τil) mittels der jeweiligen modifiziertenVerschiebematrizen V^i·n/pl aus VerfahrensschrittS00C gemäß Gleichung(23) aus dem Startvergleichszustandsvektor a_REF'(0) = a(0) offlineberechnet.In the subsequent process step S05C for prime factor p _l with high values in each case subsets a _REF '(τil) of total o each comparison state vector a _REF' (τil) by means of the respective modified Verschiebematrizen V ^{i · n / pl} from process step S00C in accordance with equation ( 23) from the start _{comparison state vector} a _REF '(0) = a (0) calculated offline.
[0101] DerVerfahrensschritt S40 gliedert sich bei der dritten Ausführungsformin einen ersten Unterverfahrensschritt S40C1, in dem der eingeleseneund in Verfahrensschritt S30 zeitlich verschobene Zustandsvektor a'(τx) für jeden großen teilerfremden Faktor p_l mit jeweils allen o Vergleichszustandsvektorena_REF'(τil) aus der Untermengea_REF''(τil) auf Identität verglichenwird.In the third embodiment, method step S40 is subdivided into a first sub-method step S40C1, in which the read-in state vector a '(τx) shifted in time in method step S30 is output for each large non-divisive factor p _l with all o comparison state vectors a _REF ' (τil) the subset a _REF '' (τil) is compared to identity.
[0102] Fallskeine Übereinstimmungzwischen dem eingelesenen, zeitlich verschobenen Zustandsvektor a'(τx) und allen o Vergleichszustandsvektorena_REF'(τil) der zumjeweiligen teilerfremden Faktor p_l gehörigen Untermengea_REF''(τil) vorliegt, wird im UnterverfahrensschrittS40C2 der eingelesene, zeitlich verschobene Zustandsvektor a'(τx) gemäß Gleichung (26) mittels derVerschiebematrix
[0103] Mitden um o·n/p_l Taktzyklen zeitlich verschobenen eingelesenenZustandsvektor a''(τx) wird im nächsten UnterverfahrensschrittS40C3 ein Vergleich mit der Untermenge a_REF''(τil)der Vergleichszustandsvektoren a_REF'(τil) anstelle eines äqivalentenVergleichs des eingelesenen, zeitlich verschobenen Zustandsvektora'(τx) mit dender Untermenge a_REF''(τil) nachfolgendeno Vergleichszustandsvektoren a_REF'(τil) hinsichtlich Identität durchgeführt.With the order o · n / p _l clock cycles time-shifted read state vector a '' (τx) in the next sub-step S40C3 a comparison with the subset a _REF '(τil) of the comparison state vector a _REF' (τil) instead of a äqivalenten comparison of the read in, temporally shifted state vector a '(τx) with the subset a _REF ''(τil) following o comparison state vectors a _REF ' (τil) performed in terms of identity.
[0104] Liegtkeine Übereinstimmungzwischen dem um o·n/p_l Taktzyklen zeitlich verschobenen, eingelesenen Zustandsvektora''(τx) und einem der insgesamt oVergleichszustandsvektoren a_REF'(τil) aus der Untermenge a_REF''(τil) vor, wird der eingelesene,und im Unterfahrensschritt S40C2 um insgesamt o·n/p_l Taktzyklenzeitlich verschobene Zustandsvektor a''(τx) im UnterverfahrensschrittS40C4 um weitere o·n/p_l Taktzyklen gemäß Gleicung (26) zeitlich verschobenund dem Vergleich mit den insgesamt o Vergleichszustandsvektorena_REF'(τil) der Untermengea_REF''(τil) in UnterverfahrensschrittS40C3 zugeführt.If there is no match between the state vector a '' (τx) read in time by o * n / p ₁ clock cycles and one of the total o comparison state vectors a _REF '(τil) from the subset a _REF ''(τil), the has been read, and the lower driving step S40C2 a total o · n / p _l clock cycles time-shifted state vector a '' (τx) in the sub-step S40C4 Gleicung (26) shifted in time according to another o · n / p _l clock cycles and the comparison with the total number o Comparison state vectors a _REF '(τil) of the subset a _REF ''(τil) in sub-step S40C3 supplied.
[0105] Wirdin einem der Unterverfahrensschritte S40C2 oder S40C4 zum eingelesenenund zeitlich verschobenen Zustandsvektor a''(τx) ein passenderVergleichszustandvektor a_REF'(τxl') aus der Untermenge a_REF''(τil) derinsgesamt o Vergleichszustandsvektoren a_REF'(τil) gefunden, so wird im nächsten Unterverfahrensschritt S50Canstelle des Verfahrensschritt S50 der ersten oder zweiten Ausführungsformdes erfindungsgemäßen Verfahrenin 2 der zum gefundenen Vergleichszustandsvektora_REF'(τil') gehörige Taktzyklus τxl' aus dem Speicherausgelesen. Aus dem fürden jeweiligen teilerfremden Faktor p_l mitgroßemWert ermittelten Taktzyklus τxl' wird entsprechendder insgesamt w durchgeführtenVerschiebe-Iterationen der tatsächlichezum jeweiligen teilerfremden Faktor p_l gehörige Taktzyklus τxl gemäß Gleichung(27) berechnet. Anschließendwird das Verfahren mit dem Verfahrensschritt S60, wie oben dargestellt,fortgefahren.Is in one of the sub steps S40C2 or S40C4 to read and time-shifted state vector a '' (τx) a matching comparison state vector a _REF '(τxl') from the subset a _REF '(τil) of the total o comparison state vector a _REF' (τil) found in the next sub-process step S50C instead of the process step S50 of the first or second embodiment of the inventive method in 2 the clock cycle τxl 'belonging to the found comparison state vector a _REF ' (τil ') is read from the memory. From the clock cycle τxl 'determined for the respective divisive factor p _l with a large value, the actual cycle cycle τxl belonging to the respective divisional factor p _l is calculated in accordance with equation (27) in accordance with the shift iteration performed overall. Subsequently, the method is continued with method step S60, as described above.
[0106] DieErfindung ist nicht auf die dargestellten drei Ausführungsformenbeschränkt.Insbesondere können inden Such- und Vergleichsoperationen der Verfahrenschritte S40, S40A,S40B3, S40C1 und S40C3 andere numerische Such- und Sprungverfahreneingesetzt werden. Auch könnendie Merkmale aller drei Ausführungsformewnvorteilhaft kombiniert werden.TheThe invention is not limited to the illustrated three embodimentslimited.In particular, inthe search and compare operations of the method steps S40, S40A,S40B3, S40C1 and S40C3 other numerical search and jump proceduresbe used. Also canthe features of all three embodiments wnbe advantageously combined.

权利要求:
Claims (11)
[1]
Verfahren zur Ermittlung der Anzahl Δτ von zwischenzwei Zeitpunkten t₁ und t₂ abgelaufenenTaktzyklen eines binärenZufallsgenerators (1), der zur Erzeugung einer binären Zufallsfolges(τi) mitZykluslängen ein Schieberegister (4) mit mindestens einer an seinenEingang (8) zurückgeführten Schieberegisterstufe(5₁ , 5₂ , .., 5_m ) umfaßt, in dem jeweils ein Zustandsvektora(τ1) unda(τ2) mitden Zuständenaller Schieberegisterstufen (5₁ , 5₂ , .., 5_m )jeweils zum Zeitpunkt t₁ und t₂ ausgelesenwird, wobei die Zustandsvektoren a(τ1) und a(τ2) jeweils mit einer gegenüber dermaximal möglichenAnzahl n von Vergleichszustandsvektoren a_REF(τi) reduziertenAnzahl n' von Vergleichszustandsvektorena_REF'(τi) verglichenwerden, wobei bei Identitätzwischen den Zustandsvektoren a(τ1)und a(τ2)und einem der n' Vergleichszustandsvektorena_REF'(τi) der jeweilszugehörige Taktzyklus τ1 und τ2 ermitteltwird und aus der Differenz der Taktzyklen τ1 und τ2 die Anzahl Δτ von abgelaufenenTaktzyklen berechnet wird.Method for determining the number Δτ of clock cycles of a binary random number generator that have elapsed between two times t ₁ and t ₂ ( 1 ), which generates a shift register () for generating a binary random sequence s (τi) with cycle length n ( 4 ) with at least one at its entrance ( 8th ) returned shift register stage ( 5 ₁ . 5 ₂ , .., 5 _m ), in which in each case a state vector a (τ1) and a (τ2) with the states of all shift register stages ( 5 ₁ . 5 ₂ , .., 5 _m ) are respectively read at the time t ₁ and t ₂ , the state vectors a (τ1) and a (τ2) each having a reduced number n 'of comparison state vectors a _REF ' compared to the maximum possible number n of comparison state vectors a _REF (τi). τi), where identity between the state vectors a (τ1) and a (τ2) and one of the n 'comparison state vectors a _REF ' (τi) the respective clock cycle τ1 and τ2 is determined and from the difference of the clock cycles τ1 and τ2 the number Δτ of elapsed clock cycles is calculated.
[2]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 1, dadurch gekennzeichnet, daß die n' Vergleichszustandsvektorena_REF'(τi) sämtlichezu allen teilerfremden Faktor p_j der Zykluslänge n jeweilsgehörigenVergleichszustandsvektoren a_REF'(τi) = a_REF'(τi·n/p_l)umfassen, wobei i jeweils eine ganzzahlige Laufvariable zwischen0 und p_l darstellt.Method for determining the number of expired clock cycles of a binary random number generator according to Claim 1, characterized in that the n 'comparison state vectors a _REF ' (τi) all comparison state vectors a _REF '(τi) = a corresponding to all non-divisive factor p _{j of} the cycle length n _REF '(τ i * n / p _l ), where i represents an integer variable between 0 and p _l .
[3]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 2, dadurch gekennzeichnet, daß die zuden Zeitpunkten t₁ und t₂ ausgelesenenZustandsvektoren a(τ1)und a(τ2) über Transformationenfür jedenteilerfremden Faktor p_l der Zykluslänge n jeweilszu Zustandsvektoren a(τ1·n/p_l) und a(τ2·n/p_l) zeitlich verschoben werden, um sie anschließend für jedenteilerfremden Faktor p_l mit allen Vergleichszustandsvektorena_REF'(τil) zu vergleichenund bei Identitätzwischen den zeitlich verschobenen Zustandsvektoren a(τ1·n/p_l) und a(τ2·n/p_l) und einem der Vergleichszustandsvektorena_REF'(τil) die zugehörigen Taktzyklen τ1l und τ2l zu ermitteln,die jeweils dem Moduluswert der Division des Taktzykluses τ1 und τ2 durch denteilerfremden Faktor p_l entsprechen.Method for determining the number of expired clock cycles of a binary random number generator according to Claim 2, characterized in that the state vectors a (τ1) and a (τ2) read at the times t ₁ and t _{2 are} transformed by transformations for each non-divisive factor p _{l of} the cycle length n in each case to state vectors a (τ1 · n / p _l ) and a (τ2 · n / p _l ) are shifted in time to then compare them for each non-divisive factor p _l with all comparison state vectors a _REF '(τil) and identity between the time-shifted state vectors a (τ1 · n / p _l ) and a (τ2 · n / p _l ) and one of the comparison state vectors a _REF '(τil) to determine the associated clock cycles τ1l and τ2l, respectively the modulus value of the division of the clock cycle τ1 and τ2 by the non-divisive factor p _l .
[4]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 3, dadurch gekennzeichnet, daß die denZeitpunkten t₁ und t₂ entsprechendenTaktzyklen τ1und τ2 jeweilsaus allen zu den jeweiligen teilerfremden Faktoren p_l gehörigen Moduluswerten τ1l und τ2l durchiterative Berechnung ermittelt werden.Method for determining the number of expired clock cycles of a binary random number generator according to Claim 3, characterized in that the clock cycles τ1 and τ2 corresponding to the time points t ₁ and t _{2 are} respectively calculated from all modulus values τ1l and τ2l belonging to the respective divisive factors p _l be determined.
[5]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet,daß derZeitpunkt t₁ der Initialisierungszeitpunktdes binärenZufallsgenerators (1) ist, der zugehörige Zustandsvektor a(0) eindie Initilisierungswerte der Schieberegisterstufen (5₁ , 5₂ ,.., 5_m ) beinhaltender Zustandsvektorist, der zugehörigeTaktzyklus τ1Null ist und die Anzahl Δτ der abgelaufenenTaktzyklen dem Taktzyklus τ2entspricht.Method for determining the number of expired clock cycles of a binary random number generator according to one of Claims 1 to 4, characterized in that the time t _{1 is} the initialization time of the binary random number generator ( 1 ), the associated state vector a (0) indicates the initialization values of the shift register stages ( 5 ₁ . 5 ₂ , .., 5 _m ), the associated clock cycle τ1 is zero and the number Δτ of the elapsed clock cycles corresponds to the clock cycle τ2.
[6]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß die einzelnenzum jeweiligen teilerfremden Faktor p_l gehörigen Vergleichszustandsvektorena_REF'(τil) mit einemiterativen Berechnungsverfahren sukzessive berechnet und mit denbeiden zu den Zeitpunkten t₁ und t₂ ausgelesenen und für jeden teilerfremden Faktorp_l zeitlich verschobenen Zustandsvektorena(τ1·n/p_l) und a(τ2·n/p_l) verglichen werden, bis Identität zwischendem jeweils iterativ berechneten Vergleichszustandsvektor a_REF'(τil) und denZustandsvektoren a(τ1·n/p_l) und a(τ2·n/p_l) besteht.Method for determining the number of expired clock cycles of a binary random-number generator according to one of Claims 1 to 5, characterized in that the individual comparison-state vectors a _REF '(τil) belonging to the respective non-divisive factor p _{1 are} successively calculated with an iterative calculation method and combined with the two the times t ₁ and t ₂ read and for each prime factor p _l time-shifted state vectors a (τ1 · n / p _l) and a (τ2 · n / p _l) are compared to identity between the iteratively calculated each comparison state vector a _REF '(τil) and the state vectors a (τ1 · n / p _l ) and a (τ2 · n / p _l ).
[7]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet,daß alleVergleichszustandsvektoren a_REF'(τil) vorab berechnet und abgepeichertwerden und anschließendmit den Zustandvektoren a(τ1·n/p_l) und a(τ2·n/p_l) verglichen werden, bis für jedenteilerfremden Faktor p_l Identität zwischeneinem der abgespeicherten Vergleichszustandsvektoren a_REF'(τil) und den Zustandsvektorena(τ1·n/p_l) und a(τ2·n/p_l) besteht.Method for determining the number of expired clock cycles of a binary random number generator according to one of Claims 1 to 5, characterized in that all the comparison state vectors a _REF '(τil) are calculated and stored in advance and then combined with the state vectors a (τ1 * n / p _l ) and a (τ2 · n / p _l ) until, for each non-alien factor p _l, identity between one of the stored comparison state vectors a _REF '(τil) and the state vectors a (τ1 * n / p _l ) and a (τ2 * n / p _l ).
[8]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 7, dadurch gekennzeichnet, daß der Vergleichzwischen den abgespeicherten Vergleichszustandsvektoren a_REF'(τil)) undden Zustandvektoren a(τ1·n/p_l) und a(τ2·n/p_l) überbinäreSuchalgorithmen mittels Entscheidungsbaum oder über Hash-Algorithmen erfolgt.Method for determining the number of expired clock cycles of a binary random number generator according to Claim 7, characterized in that the comparison between the stored comparison state vectors a _REF '(τil)) and the state vectors a (τ1 * n / p _l ) and a (τ2 * n / p _l ) via binary search algorithms by means of decision tree or via hash algorithms.
[9]
Verfahren zur Ermittlung der Anzahl von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 7 oder 8, dadurch gekennzeichnet,daß beigroßenteilerfremden Faktoren p_l nur eine Teilmenge a_REF'(τil) der Vergleichszustandsvektorena_REF'(τil) vorabberechnet, abgespeichert und anschließend mit den Zustandsvektorena(τ1·n/p_l) und a(τ2·n/p_l) verglichen wird und die Zustandsvektorena(τ1·n/p_l) und a(τ2·n/p_l) anschließend solange um eine der Teilmengea_REF'(τil) der Vergleichsvektorena_REF'(τil) entsprechendendeAnzahl o·n/p_l von Schiebeschritten zeitlich verschobenund wiederum mit der Teilmenge a_REF''(τil)der Vergleichszustandsvektoren a_REF'(τil) verglichen werden, bis Identität zwischeneinem in der Teilmenge a_REF''(τil)abgespeicherten Vergleichszustandsvektoren a_REF'(τil) und beiden Zustandsvektorena(τ1·n/p_l) und a(τ2·n/p_l) besteht.A method for determining the number of elapsed clock cycles of a binary random number generator according to claim 7 or 8, characterized in that for large non-divisive factors p _l only a subset a _REF '(τil) of the comparison state vectors a _REF ' (τil) calculated in advance, stored and then is compared with the state vectors a (τ1 · n / p _l ) and a (τ2 · n / p _l ), and the state vectors a (τ1 · n / p _l ) and a (τ2 · n / p _l ) are then compared by one the subset a _REF '(τil) of the comparison vectors a _REF ' (τil) corresponding number o · n / p _l shifted by sliding steps and again with the subset a _REF '' (τil) of the comparison state vectors a _REF '(τil) are compared until there is identity between a in the subset a _REF '' stored (τil) Comparative state vectors a _REF '(τil) and two state vectors a (τ1 · n / p _l) and a (τ2 · n / p _l).
[10]
Vorrichtung zur Ermittlung der Anzahl Δτ von zwischenzwei Zeitpunkten t₁ und t₂ abgelaufenenTaktzyklen eines binärenZufallsgenerators (1) mit einem binären Zufallsgenerator (1),der zur Erzeugung einer binärenZufallsfolge s(τi)mit Zykluslängen ein Schieberegister (4) mit mindestens einer an seinenEingang (8) zurückgeführten Schieberegisterstufe(5₁ , 5₂ ,.., 5_m ) umfaßt, und einer Prozessor-Einheit(10), die übereine Ein-/Ausgabe-Baugruppe(9) die Binärzustände allerSchieberegisterstufen (5₁ , 5₂ , .., 5_m )zu den Zeitpunkten t₁ und t₂ einliest,jeweils zu einem Zustandsvektor a(τ1) und a(τ1) zusammenfaßt und dieZustandsvektoren a(τ1)und a τ2)jeweils mit einer in einem Speicher (11) abgelegten, gegenüber dermaximal möglichenAnzahl n von Vergleichszustandsvektoren a_REF(τi) reduziertenAnzahl n' von Vergleichszustandsvektorena_REF'(τil) vergleichtund bei Identitätzwischen den Zustandsvektoren a(τ1)und a(τ2)und dem Vergleichszustandsvektor a_REF'(τil) den jeweils zugehörigen Taktzyklus τ1 und τ2 zur Ermittlungder Anzahl Δτ von abgelaufenenTaktzyklen zuweist.Device for determining the number Δτ of clock cycles of a binary random number generator expired between two times t ₁ and t ₂ ( 1 ) with a binary random number generator ( 1 ), which generates a shift register () for generating a binary random sequence s (τi) with cycle length n ( 4 ) with at least one at its entrance ( 8th ) returned shift register stage ( 5 ₁ . 5 ₂ , .., 5 _m ) and a processor unit ( 10 ) via an input / output module ( 9 ) the binary states of all shift register stages ( 5 ₁ . 5 ₂ , .., 5 _m ) at the times t ₁ and t ₂ , in each case to a state vector a (τ1) and a (τ1) summarizes and the state vectors a (τ1) and a τ2) each with one in a memory ( 11 ) compared to the maximum possible number n of comparison state vectors a _REF (τi) reduced number n 'of comparison state vectors a _REF ' (τil) compares and identity between the state vectors a (τ1) and a (τ2) and the comparison state vector a _REF ' (τil) assigns the respective associated clock cycle τ1 and τ2 for determining the number Δτ of elapsed clock cycles.
[11]
Vorrichtung zur Ermittlung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators nach Anspruch 10, dadurch gekennzeichnet, daß die Vorrichtungzusätzlicheine Anzeige-Einrichtung (3) zur Darstellung der Anzahl Δτ von abgelaufenenTaktzyklen eines binärenZufallsgenerators (1) enthält.Device for determining the number Δτ of elapsed clock cycles of a binary random number generator according to claim 10, characterized in that the device additionally comprises a display device ( 3 ) for representing the number Δτ of elapsed clock cycles of a binary random number generator ( 1 ) contains.

类似技术:

---

公开号 | 公开日 | 专利标题

---

DE102012015423B4|2015-02-26|Method and sensor system for capacitive measurement of the properties of a transmission path of a measuring system between a transmitter electrode and a receiver electrode

---

Nerlove1971|Further evidence on the estimation of dynamic economic relations from a time series of cross sections

---

Lenstra et al.1990|The number field sieve

---

Peköz et al.2013|Degree asymptotics with rates for preferential attachment random graphs

---

DE10015384B4|2004-02-12|A / D conversion device, calibration unit and method therefor

---

DE60215332T2|2007-05-24|System and method for sharing a common secret

---

Li et al.2004|On a class of renewal risk models with a constant dividend barrier

---

Watson1961|Goodness-of-fit tests on a circle

---

DE202016107476U1|2017-01-23|Batch processing in a neural network processor

---

DE60204708T2|2006-05-04|HASH-BASED PSEUDO-FALL-NUMBER GENERATOR

---

Michael et al.1976|Generating random variates using transformations with multiple roots

---

DE102004036880B4|2012-04-19|Method and apparatus for reducing noise in an MCM signal

---

EP2605445A1|2013-06-19|Verfahren und Vorrichtung zur Absicherung von Blockchiffren gegen Template-Attacken

---

Sauer et al.1993|How many delay coordinates do you need?

---

DE10303475B3|2004-10-07|Maximum likelihood estimation of the channel coefficients and the DC offset in a digital baseband signal of a radio receiver using the SAGE algorithm

---

DE602004008516T2|2008-05-15|METHOD AND CIRCUIT FOR GENERATING RANDOM COUNTERS AND COMPUTER PROGRAM PRODUCT THEREFOR

---

DE102011080656B4|2013-11-14|Method for homogenizing the threshold values of a multichannel quantum-counting radiation detector

---

EP1540880B1|2006-03-08|Geschützte kryptographische berechnung

---

DE112016002298T5|2018-02-15|PREVIEW OF WEIGHTS FOR USE IN A NEURONAL NETWORK PROCESSOR

---

DE102013221950A1|2014-05-08|Multi-carrier particle beam writing method and multiple-carrier particle beam writing apparatus

---

EP0123921B1|1990-11-28|Parallelverknüpfungsschaltung mit verkürztem Übertragsdurchlauf

---

DE3917059A1|1989-12-07|CORDIC ARRANGEMENT FOR MULTIPLICATING COMPLEX NUMBERS

---

DE3700991C2|1996-02-01|Digital carry look ahead adder

---

DE102010028266A1|2011-10-27|Control device and method for calculating an output for a controller

---

WO2004013839A1|2004-02-12|Vorrichtung und verfahren zum erzeugen einer komplexen spektraldarstellung eines zeitdiskreten signals

同族专利:

---

公开号 | 公开日

---

EP1594229A1|2005-11-09|

---

EP1594229B1|2009-06-17|

---

DE102004022647B4|2015-07-09|

---

DE502005007486D1|2009-07-30|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

法律状态:
2005-12-22| OR8| Request for search as to paragraph 43 lit. 1 sentence 1 patent law|

---

2011-06-22| R012| Request for examination validly filed|Effective date: 20110407 |

---

2012-02-07| R016| Response to examination communication|

---

2014-08-01| R016| Response to examination communication|

---

2015-03-24| R018| Grant decision by examination section/examining division|

---

2016-04-12| R020| Patent grant now final|

---

2020-12-01| R119| Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal fee|

优先权:

---

申请号 | 申请日 | 专利标题

---

DE102004022647.4A|DE102004022647B4|2004-05-07|2004-05-07|Method and device for determining the number of expired clock cycles of a binary random number generator|DE102004022647.4A| DE102004022647B4|2004-05-07|2004-05-07|Method and device for determining the number of expired clock cycles of a binary random number generator|

---

EP05009352A| EP1594229B1|2004-05-07|2005-04-28|Verfahren und Vorrichtung zur Ermittlung der Anzahl von abgelaufenen Taktzyklen eines binären Zufallsgenerators|

---

DE200550007486| DE502005007486D1|2004-05-07|2005-04-28|Method and device for determining the number of expired clock cycles of a binary random number generator|